Мы знакомы с последовательностью Фибоначчи (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 ≤ 2^31 - 1) и (i ≤ j и j-i ≤ 10000). Можно также предположить, что i и j будут индексами существующей элементов строки (т.е. 0 ≤ i, j < length of BFS(N)).
Для каждого заданного теста вывести искомую подстроку BFS(N) с i-го по j-й символ в отдельной строке.