In mathematics, often used the so-called recurrence relations. Usually they are used to define sequences of numbers, but can also be applied to define the sequence of rows.
One example of lines defined by the recurrence relation is Fibostrings
F0 = a,
F1 = b, ... . They are defined as follows:
F0 = a, F=b,
Fi-2Fi-1, i > 1. The first seven strings of Fibonacci as follows: a, b, ab, bab, abbab, bababbab, abbabbababbab.
Dima is engaged in the group Olympiad programming and are interested in algorithms on strings. He recently learned about the Fibonacci strings. He quickly realized that their length with increasing number i is growing very quickly, so the task of finding all the characters of
Fi requires too much memory. He therefore decided to limit the problem of finding some characters..
Write a program that finds the k-th character strings
The first line contains the number of test cases t (1 ≤ t ≤ 100). Each of the following t lines contains two integers n and k (0 ≤ n ≤ 45, 1 ≤ k ≤ |
Fn|, where |
Fn| is the length of the string
Fn, character positions in the line are numbered from one).
Print t lines, each contains exactly one character - the answer to an appropriate test case.
4 0 1 1 1 3 2 7 7
a b a a