odd doctor 已更新

Interesting Set

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
23.08%(3/13)
Description:

Mr.Frog is researching integers.

He converts two integers X and Y into binary without leading zeros, if they have the same quantity of 0
and the same quantity of 1 in the binary, Mr.Frog will think these two integers are friendly.
For example, 5(10) = 101(2) and 6(10) = 110(2), both of them have two 1 and one 0 in the binary, so
Mr.Frog thinks 5 and 6 are friendly.
Now, Mr.frog gets an integer N and defines a sorted set S. The sorted set S consists of integers which
are friendly with N and bigger than N. He wants to know what is the Kth integer in S.
Because Mr.Frog is on his way back from Hong Kong to Beijing, he wants to ask you for help.


Input:

The first line contains an integer T, where T is the number of test cases. T test cases follow.

For each test case, the only line contains tow integers N and K.

1<=T<=200

1<=N<=1018

1<=K<=1018

Output:

For each test case, print one line containing “Case #x: y”, where x is the test case number (starting
from 1) and y is the Kth integer in the sorted set S. If the integer he wants to know does not exist, y is
“IMPOSSIBLE”.

Sample Input:
2
9 2
7 4
Sample Output:
Case #1: 12
Case #2: IMPOSSIBLE
Hint:

For the first case, the sorted set S will be {10,12}, so the 2nd integer is 12.
For the second case, the sorted set S will be ∅, so the answer is “IMPOSSIBLE”.


Submit