Trinomial

Consider the trinomial $(x^2 + x + 1)^n$. We study the coefficients $c_i$ that appear when this expression is expanded:

$c_0 + c_1 x + c_2 x^2 + \dots + c_{2n} x^{2n}$

For example, $(x^2 + x + 1)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6$.

Write a program that:

• reads several data sets, each consisting of two numbers $n$ and $i$,
• for each data set computes $c_i \bmod 3$, where $c_i$ is the coefficient of $x^i$ in the expansion of $(x^2 + x + 1)^n$,
• writes each computed value to the standard output.

The first line contains one integer $k$, the number of data sets, where $1 \le k \le 10000$.

It is followed by $k$ data sets, one per line. Each set consists of two non-negative integers $n$ and $i$ separated by a single space, where $0 \le n \le 10^{15}$ and $0 \le i \le 2n$.

Output $k$ lines. The $j$-th line must contain a single non-negative integer equal to $c_i \bmod 3$ for the $j$-th data set.