시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB1814888.889%

문제

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

c0+c1x+c2x2+…+c2nx2n

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.

입력

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.

예제 입력 1

5
2 0
7 4
4 5
5 3
8 15


예제 출력 1

1
2
1
0
2