Fibonacci String

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}$, where $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

The first line contains the number of test cases $t$ $(1\le t\le 100)$. Each of the following $t$ lines contains two integers $n$ and $k$ $(0\le n\le 45,1\le k\le |F_n|)$, where $|F_n|$ is the length of the string $F_n$, character positions in the line are numbered from one.

Output

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

Examples