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

Описание

В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк. Одним из примеров строк, задаваемы рекуррентным соотношением являются строки Фибоначи F0,F1,... Они задаются следующим образом: F ₀ = a, F ₁ = b, F _i = F _i−2 F _i−1 ,i > 1. Первые семь строк Фибоначчи выглядят следующим образом:a,b,ab,bab,abbab,bababbab,abbabbababbab. Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера i растет очень быстро, поэтому задача нахождения всех символов строки F _i требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов. Напишите программу, которая находит k-ый символ строки Fi .

Формат входных данных

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

Формат выходных данных

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