Bruce and Natasha are playing a game. To win the game, Bruce needs to correctly guess a binary string after hearing some clues from Natasha.
A binary string is string comprising of only 1s and 0s. The length of the string is known to be less than or equal to 50. To help Bruce, Natasha gives him the following clues - 1. The last bit of the string 2. Lexicographic rank of the string among all its permuatations 3. Lexicographic rank of the inverted string among all its permutations (Inverted string is the string obtained by flipping all bits of the original string)
For example, lexicographic rank of 001 is 1; 010 is 2; 100 is 3.
Bruce is in a bit of a trouble and needs your help to win the game. If no binary string exists with length less than or equal to 50 that satisfies all the clues, print "IMPOSSIBLE" (without quotes). If multiple such binary strings exist, print "MULTIPLE" (without quotes). Else print the only binary string with length less than or equal to 50 that satisfies these clues.
Input:
First line of the input contains T (1<=T<=100), the number of test cases. The next T lines each contain 3 space separated integers. First integer is 0 or 1 and denotes the last bit of the binary string. Second integer denotes R (1<=R<=1015) denoting the rank of the binary string. Third integer denotes S (1<=S<=1015) denoting the rank of the inverted string.
Output:
Output T lines with each line containing MULTIPLE, IMPOSSIBLE or a binary string as described above.
For the first test case, both 0 and 00 are valid binary strings among many others that satisfy all the clues. Similarly, for the second test case, both 1 and 11 are valid binary strings that satisfy all the clues. No binary string of length less than or equal to 50 satisfies all the clues of the third test case. For fourth test case, 1011 is the only binary string that satisfies all the clues among all binary strings of length less than or equal to 50.
