eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci String

Fibonacci String

Time limit 1 second
Memory limit 128 MiB

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 F[0] = a, F[1] = b, ... . They are defined as follows: F[0] = a, F[1]=b, F[i] = F[i-2]F[i-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 F[i] 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 F[i].

Input data

The first line contains the number of test cases t (1t100). Each of the following t lines contains two integers n and k (0n45, 1k ≤ |F[n]|, where |F[n]| is the length of the string F[n], character positions in the line are numbered from one).

Output data

Print t lines, each contains exactly one character - the answer to an appropriate test case.

Examples

Input example #1
4
0 1
1 1
3 2
7 7
Output example #1
a
b
a
a
Source 2009 Цикл интернет-олимпиад для школьников. First olympiad, base level, September 19, Problem C