e-olymp
Задачи

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

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

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи F0 = a, F1 = b, ... . Они задаются следующим образом: F0 = a, F1 = b, Fi = Fi-2Fi-1, i >1. Первые семь строк Фибоначчи выглядят следующим образом: a, b, ab, bab, abbab, bababbab, abbabbababbab.

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

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

Входные данные

Первая строка содержит количество тестов t (1t100). Каждая из следующих t строк содержит два целых числа n и k (0n45, 1k ≤ |Fn|, через |Fn| обозначена длина строки Fn, позиции символов в строке нумеруются с единицы).

Выходные данные

Выведите t строк, каждая из которых содержит k-ый символ строки Fn.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
0 1
1 1
3 2
7 7
Выходные данные #1
a
b
a
a
Источник 2009 Цикл интернет-олимпиад для школьников. Первая олимпиада, базовый уровень, 19 сентября, Задача C