题目描述

求 $(x^2+x+1)^n$ 的第 $i$ 项系数。

输入格式

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

接下来的 $k$ 行，每行两个整数 $n,i$。

输出格式

对于每组数据，输出 $x_i \bmod 3$ 之后的结果。

5
2 0
7 4
4 5
5 3
8 15

1
2
1
0
2

提示

对于 $100\%$ 的数据，$1 \le k \le 10000$，$0\le n\le 10^{15}$，$0\le i\le 2\times n$。