题目描述

给定一个多项式 $f(x) = (x^2 + x + 1)^n$，展开后的每一项按多项式次数由高到低排序，求它的第 $k$ 项系数，答案对 $3$ 取余。

比如 $n = 1, k = 0$ 时，$x^2$ 为第 $0$ 项，系数为 $1$，答案为 $1 \% 3 == 1$。

输入格式

第一行，输入 $T$，表示数据组数。

接下来 $T$ 行，每行输入 $n$ 和 $k$。

• $1 \leq T \leq 10^4$
• $0 \leq n \leq 10^{15}, 0 \leq k \leq 2n$

输出格式

对于每组询问，输出系数模 $3$ 后的结果。

样例输入

5
2 0
7 4
4 5
5 3
8 15

样例输出

1
2
1
0
2