Problem Description

Find the coefficient of the $i$-th term of $(x^2 + x + 1)^n$.

Input Format

The first line contains an integer $k$, the number of test cases.

The next $k$ lines each contain two integers $n, i$.

Output Format

For each test case, output the result of $x_i \bmod 3$.

5
2 0
7 4
4 5
5 3
8 15

1
2
1
0
2

Hint

Constraints: for $100\%$ of the testdata, $1 \le k \le 10000$, $0 \le n \le 10^{15}$, and $0 \le i \le 2 \times n$.

Translated by ChatGPT 5