Recently, Hungar is studying binary numbers. But he faces a problem, he wants to know the Kth (K <= 10,000,000) binary numbers whose sum of all '1' digits is N (1 <= N <= 10).

There are several test cases.
The first line, an integer T indicates the test cases.
Next T lines, two integers K, N as mentioned above.

Output the Kth number in the binary number form.