Recursive Strings
-----------------

Consider the sequence of strings defined as follows.

s(0) = 0
s(1) = 1
s(n) = s(n-1)s(n-2) for n >= 2.

Note that s(n) is formed by concatenating the previous two strings together.
You want to compute the character that appears in a certain position of
one of these strings.

Input
-----

The input will consist of multiple instances.  The first line will contain
a single positive integer m, indicating that there are m instances in the
input.

This will be followed by m lines, each containing a non-negative integer
n (0 <= n <= 60) and a positive integer k.

Output
------

For each input pair n and k, output the kth character of string s(n).
You may assume that k is less than or equal to the number of characters
in string s(n).

Sample Input
------------

3
5 2
0 1
4 3

Sample Output
-------------

0
0
1