eolymp
bolt
Try our new interface for solving problems
Problems

BFS (Binary Fibonacci String)

BFS (Binary Fibonacci String)

Time limit 1 second
Memory limit 64 MiB

We are familiar with the Fibonacci sequence (1, 1, 2, 3, 5, 8, ...). What if we define a similar sequence for strings? Sounds interesting? Let's see.

We define the follwing sequence:

BFS(0) = 0BFS(1) = 1 (here "0" and "1" are strings, not simply the numerical digit, 0 or 1)

for all (n > 1) BFS(n) = BFS(n - 2) + BFS(n - 1) (here, + denotes the string concatenation operation). (i.e. the n-th string in this sequence is a concatenation of a previous two strings).

So, the first few strings of this sequence are: 0, 1, 01, 101, 01101, and so on.

Your task is to find the N-th string of the sequence and print all of its characters from the i-th to j-th position, inclusive. (All of N, i, j are 0-based indices)

Input data

The first line of the input file contains an integer T (T100) which denotes the total number of test cases. The description of each test case is given below:

Three integers N, i, j (0N, i, j2^31 - 1) and (ij and j-i10000). You can assume that, both i and j will be valid indices (i.e. 0i, j < length of BFS(N)).

Output data

For each test case, print the substring from the i-th to the j-th position of BFS(N) in a single line.

Examples

Input example #1
3
3 1 2
1 0 0
9 5 12
Output example #1
01
1
10101101