Мы знакомы с последовательностью Фибоначчи (1, 1, 2, 3, 5, 8, ...). А что будет, если мы определим аналогичную последовательность для строк? Звучит интересно? Давайте посмотрим.

Мы определим эту последовательность так:

BFS(0) = 0

BFS(1) = 1 (здесь "0" и "1" являются строками, а не просто числами 0 или 1)

для всех (n > 1)

BFS(n) = BFS(n - 2) + BFS(n - 1) (здесь + обозначает операцию конкатенации). (то есть, n-ая строка в этой последовательности представляет собой объединение двух предыдущих строк).

Итак, первые несколько строк в этой последовательности такие: 0, 1, 01, 101, 01101 и так далее.

Ваша задача: для каждой заданной n-ой строки этой последовательности найти и вывести все её элементы с i-ой по j-ую позицию включительно (все числа n, i, j нумеруются начиная с 0).

Входные данные

Первая строка содержит количество тестов t (t ≤ 100). Описание каждого теста имеет вид:

Три целых числа n, i, j (0 ≤ n, i, j ≤ 231 - 1) и (i ≤ j и j - i ≤ 10000). Можно также предположить, что i и j будут индексами существующих элементов строки (т.е. 0 ≤ i, j < length_ of BFS(n)).

Выходные данные

Для каждого теста вывести искомую подстроку BFS(n) с i-го по j-ый символ в отдельной строке.