Cisco OA 2022 - B-Restricted Strings
Alice and her friends are participating in a CISCO hackathon where they are tasked with a programming problem involving strings. The challenge is to generate strings of length N using the characters 'A' and 'B', with the restriction that two consecutive 'B's are not allowed.
Requirements
- Alice's team can generate any number of strings that satisfy the above condition.
- All valid strings must be sorted in lexicographical order.
- Given a specific index M, the team must output the string that appears at 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".