Строки Фибоначчи
В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк.
Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи F[0] = a, F[1] = b, ... . Они задаются следующим образом: F[0] = a, F[1] = b, F[i] = F[i-2]F[i-1], i > 1. Первые семь строк Фибоначчи выглядят следующим образом: a, b, ab, bab, abbab, bababbab, abbabbababbab.
Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера n растет очень быстро, поэтому задача нахождения всех символов строки F[n] требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.
Напишите программу, которая находит k-ый символ строки F[n].
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждая из следующих t строк содержит два целых числа n и k (0 ≤ n ≤ 45, 1 ≤ k ≤ |F[n]|, через |F[n]| обозначена длина строки F[n], позиции символов в строке нумеруются с единицы).
Выходные данные
Выведите t строк, каждая из которых содержит k-ый символ строки F[n].