Poi2003 Trinomial

考虑一个多项式 $(x^2 + x + 1)^n$，我们对它展开式中的系数 $c_i$ 很感兴趣：

$$(x^2+x+1)^n = 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.$$

输入格式

第一行一个数 $k$，表示数据的组数。

接下来 $k$ 组数据，每组两个非负整数 $n$ 和 $i$。

输出格式

对于每组数据，输出 $c_i$ 对 $3$ 取模以后的结果。

样例输入

5
2 0
7 4
4 5
5 3
8 15

样例输出

1
2
1
0
2

数据范围

• $1\le k\le 10^4$；
• $0\le n\le 10^{15}$；
• $0\le i\le 2n$。

来源与许可

本题为 POI 2003 试题「Trinomial」，题面与测试数据整理自 BZOJ 1436。

样例 1

输入

5
2 0
7 4
4 5
5 3
8 15

输出

1
2
1
0
2