Lucky Ticket#6366
While traveling on public transport in Colorovia, our heroes noticed an interesting feature: all tickets had numbers made up only of zeros and ones. A ticket is considered lucky if its number does not contain three consecutive zeros.
Mr. Kotsky became curious about this and wondered: if a ticket number has digits, what is the number of the -th lucky ticket?
The first line of the input contains the number of test cases (1 \le T \le 10000).
Each of the following lines contains a test case with two integers: (1 \le N \le 50) and .
For each test case, output the -th lexicographically ordered lucky sequence of length . It is guaranteed that there are at least lucky sequences.
Example 1