29564번 - Строки Фибоначчи 다국어

문제

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

Одним из примеров строк, задаваемы рекуррентным соотношением являются строки Фибонначи $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$ строк, каждая из которых должна содержать ровно один символ --- ответ для соответствующего набора входных данных.

제한

힌트