Lucky Ticket

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 N digits, what is the number of the K-th lucky ticket?

Input

The first line of the input contains the number of test cases T (1 ≤ T ≤ 10000).

Each of the following T lines contains a test case with two integers: N (1 ≤ N ≤ 50) and K.

Output

For each test case, output the K-th lexicographically ordered lucky sequence of length N. It is guaranteed that there are at least K lucky sequences.

Examples