Строки Фибоначчи

В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк.

Одним из примеров строк, задаваемы рекуррентным соотношением являются строки Фибонначи $F\_0$, $F\_1$, $\ldots$ Они задаются следующим образом: $F\_0=a$, $F\_1=b$, $F\_i=F\_{i-2}F\_{i-1}, i > 1$. Первые семь строк Фибоначчи выглядят следующим образом: a, b, ab, bab, abbab, bababbab, abbabbababbab.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $i$ растет очень быстро, поэтому задача нахождения всех символов строки $F\_i$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F\_i$.

Входной файл содержит несколько наборов входных данных. Первая строка входного файла содержит целое число $T$ наборов входных данных ($1 \le T \le 100$). Каждая из последующих $T$ строк описывает один набор входных данных и содержит по два целых числа: $n$ и $k$ ($0 \le n \le 45$, $1 \le k \le |F\_n|$, как $|F\_n|$ обозначена длина строки $F\_n$, позиции символов в строке нумеруются с единицы).

Выведите в выходной файл $T$ строк, каждая из которых должна содержать ровно один символ --- ответ для соответствующего набора входных данных.