Sequence
Easy
Execution time limit is 2 seconds
Runtime memory usage limit is 64 megabytes
A sequence is considered "good" if it does not contain three consecutive zeros.
Input
The first line of the input contains the number of test cases, t (1 ≤ t ≤ 10000). Each test case consists of two integers: n (1 ≤ n ≤ 50) and k.
Output
For each test case, output the k-th good sequence of length n in lexicographical order.
It is guaranteed that there are at least k good sequences available.
Examples
Input #1
Answer #1
Submissions 270
Acceptance rate 20%