Skip to main content

Cisco

Cisco OA-1 2022

Problem Description

Alice and her friends are taking part in a CISCO hackathon, where they face a programming challenge centered around strings. Their objective is to create strings of length N using the characters 'A' and 'B', ensuring that no two 'B's are adjacent.

Requirements:

  • The team can produce any number of valid strings that meet this condition.
  • All valid strings must be arranged in lexicographical order.
  • Given a specific index M, the team needs to provide the string that corresponds to that index in the sorted list of valid strings.

Input Format

  • The first line contains an integer T — the number of test cases.
  • For each test case, there are two integers N and M:
    • N — the length of the strings.
    • M — the 1-based index of the desired string.

Constraints

  • 1≤T≤10
  • 1≤N≤100
  • 1≤M≤10^9

Output Format

For each test case, output the string at the M-th index if it exists; otherwise, output "Not Possible".

Example Input:
2
2 3
2 4

Example Output:
BA
Not Possible

Explanation

  • For N=2, the valid strings are 'AA', 'AB', and 'BA'. The 3rd string is 'BA'.
  • For N=2, there are only 3 valid strings, so asking for the 4th string results in "Not Possible".