#1436. Poi2003 Trinomial

内存限制:64 MiB 时间限制:5 Sec

题目描述

考虑一个多项式(x2 + x + 1)^n. 我们对展开式中的系数ci 很感兴趣: 
C0 + C1x + C2x^2 + ... + C2n x^2n 
举个例子, (x^2 + x + 1)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6.

输入格式

第一行一个数k 表示数据的组数, 1 <= k <= 10000. 
然后接下来k 组数据, 每组两个非负整数n 和 i, 
0 <= n <= 1000000000000000, 0 <= i <= 2n.

输出格式

对于每组数据,输出ci 模3 以后的结果.

样例

样例输入


			
5
2 0
7 4
4 5
5 3
8 15

样例输出


			
1
2
1
0
2

数据范围与提示