求 (x2+x+1)n(x^2+x+1)^n(x2+x+1)n 的第 iii 项系数。
第一行一个数 kkk 表示数据的组数。
接下来的 kkk 行，每行两个整数 n,in,in,i。
对于每组数据，输出 xi mod 3x_i \bmod 3ximod3 之后的结果。
5 2 0 7 4 4 5 5 3 8 15
1 2 1 0 2
对于 100%100\%100% 的数据，1≤k≤100001 \le k \le 100001≤k≤10000，0≤n≤10150\le n\le 10^{15}0≤n≤1015，0≤i≤2×n0\le i\le 2\times n0≤i≤2×n。
注册一个 oirush 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 oirush 通用账户
