考虑三项式 $(x^2+x+1)^n$。我们关注该三项式展开后的系数 $c_i$：

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

例如，$(x^2+x+1)^3=1+3x+6x^2+7x^3+6x^4+3x^5+x^6$。

任务

编写一个程序，完成以下操作：

• 从标准输入读取包含数字 $n$ 和 $i$ 的数据集；
• 对于每组数据，计算 $c_i \pmod 3$，其中 $c_i$ 是三项式 $(x^2+x+1)^n$ 展开式中 $x^i$ 的系数；
• 将计算出的结果输出到标准输出。

输入格式

标准输入的第一行包含一个整数 $k$，表示数据集的数量，$1 \le k \le 10\,000$。随后有 $k$ 行数据，每行一组。每组数据包含两个非负整数 $n$ 和 $i$，中间用空格隔开，$0 \le n \le 1\,000\,000\,000\,000\,000$，$0 \le i \le 2n$。

输出格式

程序应向标准输出写入 $k$ 行。第 $j$ 行应包含一个非负整数，即第 $j$ 组数据对应的 $c_i \pmod 3$ 的结果。

样例

输入 1

5
2 0
7 4
4 5
5 3
8 15

输出 1

1
2
1
0
2