Problem: Trinomial Author: Krzysztof Sikora

Consider a trinomial (x2 + x + 1)n. We are interested in the coefficients ci of the expansion of this trinomial:

c0 + c1x + c2x2 + ... + c2n x2n

For example, (x2 + x + 1)3 = 1 + 3x + 6x2 + 7x3 + 6x4 + 3x5 + x6.

Write a program which:
• reads from the standard input sets of data that comprise numbers n and i,
• for each set of data computes ci modulo 3, where ci is the coefficient of xi in the expansion of the trinomial (x2 + x + 1)n,
• 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 ci modulo 3 for the numbers from the j-th set.

## Example

For the following input data:
```5
2 0
7 4
4 5
5 3
8 15
```
```1