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

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

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

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