eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи 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 (1t100). Каждая из следующих t строк содержит два целых числа n и k (0n45, 1k ≤ |F[n]|, через |F[n]| обозначена длина строки F[n], позиции символов в строке нумеруются с единицы).

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

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

Пример

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