12041 - BFS (Binary Fibonacci String)

我們知道費氏數列(Fibonacci sequence)：1, 1, 2, 3, 5, 8, ...。我們現在用類似的概念定義一種字串，如下所示：
 
BFS(0) = 0
BFS(1) = 1 (這裡的"0"與"1"為字串，並非數字的0與1)
對於所有 n > 1，BFS(n) = BFS(n-1) + BFS(n-1)，這裡的 + 符號表示兩個字串的合併

故我們定義了一個新的字串序列：0, 1, 01, 101, 01101, ...。
請你寫一個程式找出序列中的第N個字串，並輸出該字串的第 i 個字元到第 j 個字元(N, i, j的序號皆以0開始)。

Input

輸入資料的第一列有一個整數T(T <= 100)表示測試資料的組數，每組資料有三個整數N, i, j (0 <= N, i, j < 2^31 且 i <= j 且 j - i <= 10000)，資料保證不會超出範圍(即 0 <= i, j < BFS(N)字串長度)。

Output

對於每組測試資料，請輸出BFS(N)中從 i ~ j 位置的字串。

Sample Input

3

3 1 2

1 0 0

9 5 12

Sample Output

01

1

10101101

原文出處