Try our new interface for solving problems

Fibonacci String

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 F0 = a, F1 = b, ... . They are defined as follows: F0 = a, F[1]=b, Fi = 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 Fi.


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 ≤ |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.

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