Consider a trinomial (x²+x+1)ⁿ. We are interested in the coefficients c_i of the expansion of this trinomial:</p>

c₀+c₁x+c₂x²+…+c_2nx²ⁿ

For example, (x²+x+1)³=1+3x+6x²+7x³+6x⁴+3x⁵+x⁶.

Write a program which:

• reads from the standard input sets of data that comprise numbers n and i,
• for each set of data computes c_i modulo 3, where c_i is the coefficient of xⁱ in the expansion of the trinomial (x²+x+1)ⁿ,
• for each set of data writes the computed number to the standard output.

In the first line of the standard input there is one integer k denoting the number of the data sets, 1 ≤ k ≤ 10,000. It is followed by k sets of data, one per line. Each set consists of two non-negative integers n and i separated by a single space, 0 ≤ n ≤ 1,000,000,000,000,000, 0 ≤ i ≤ 2n.

출력 형식

One should write k lines to the standard output. The j-th line ought to contain one non-negative integer being ci modulo 3 for the numbers from the j-th set.

예제 입력

5
2 0
7 4
4 5
5 3
8 15

예제 출력

1
2
1
0
2