高斯整数(guass)

题目描述

对于任意高斯整数 $a+bi\left(a,b\in \Z\right)$，定义它的 $i-1$ 表示法为 $01$ 序列 $d_0,d_1\cdots d_m$ 使得：

• $a+bi=\sum_{j=0}^md_j\left(i-1\right)^j$
• $d_m\neq 0$，除非 $a+bi=0$，此时令 $m=0,d_0=0$

可以证明对于任意高斯整数它的 $i-1$ 表示法是唯一的。

定义 $f\left(a+bi\right)=\sum_{j=0}^md_j$，令 $G\left(L\right)=\sum_{a=-L}^{L}\sum_{b=-L}^Lf\left(a+bi\right)$

多组询问，每次给定 $L,P$ 求 $G\left(L\right)\pmod P$。

输入格式

第一行一个正整数 $T$ 代表数据组数。

后面 $T$ 行每行两个正整数，分别为 $L,P$。

输出格式

输出 $T$ 行，对于每组询问输出一个整数，为答案。

输入样例

4
1 998244353
2 998244353
500 998244353
1000000000000000 998244353

输出样例

20
75
10795060
558184759

样例解释

对于询问 $1$，$G\left(1\right)=f(-1-i)+f(-1)+f(-1+i)+f(-i)+f(0)+f(i)+f(1-i)+f(1)+f(1+i)$

这 $9$ 个数的 $i-1$ 表示法分别为 $011$，$10111$，$01$，$111$，$0$，$11$，$010111$，$1$，$0111$

对应的 $f$ 值为 $2,4,1,3,0,2,4,1,3$，和为 $20$

数据范围

对 $100\%$ 的数据，$1\le L\le 10^{18},1\le T\le 2\times 10^4,9\times 10^8\le P\le 10^9$。保证 $P$ 为素数。

每个测试点的分值为 $10$。