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

c₀ + c₁x + c₂x² + ... + c_2n x²ⁿ

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

Task

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

Input

In the first line of the standard input there is one integer k denoting the number of the data sets, 1 <= k <= 10000. 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 <= 1000000000000000, 0 <= i <= 2n.

Output

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

Example

5
2 0
7 4
4 5
5 3
8 15

1
2
1
0
2