Consider a trinomial $(x^2+x+1)^n$. We are interested in the coefficients $c_i$ of the expansion of this trinomial:

$$c_0 + c_1x + c_2x^2 + \cdots + c_{2n}x^{2n}$$

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

Task

Write a program which:

• 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_i$ in the expansion of the trinomial $(x^2+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 \le k \le 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 \le n \le 1\,000\,000\,000\,000\,000$, $0 \le i \le 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

Input

5
2 0
7 4
4 5
5 3
8 15

Output

1
2
1
0
2