Fibonacci strings#2524
In mathematics, so-called recurrence relations are often used. They are usually employed to define numerical sequences; however, they can also be used to define sequences of strings.
One example of strings defined by recurrence relations is the Fibonacci strings. They are defined as follows:
The first seven Fibonacci strings are:
Dima attends an olympiad programming club and is interested in string algorithms. Recently, he learned about Fibonacci strings and quickly noticed that as the index increases, the length of the string F_i grows very rapidly. Therefore, storing the entire string requires too much memory. As a result, Dima decided to restrict himself to the problem of finding individual characters.
Write a program that determines the -th character of the string F_n.
The first line contains the number of test cases t~(1 \le t \le 100). Each of the next lines contains two integers and k~(0 \le n \le 45, 1 \le k \le |F_n|), where |F_n| denotes the length of the string F_n. Character positions in the string are numbered starting from one.
Print lines. Each line should contain exactly one character — the answer to the corresponding test case.
Example 1