设 g(x) = f(x) * x ，多项式 A = Σ g(i) * x^i , 多项式 B = Σ f(i) * x^i。
首先，g(x) = g(x-1) + g(x-2) + f(x-1) + 2f(x-2)，所以我们可以得到: A = x * A + x^2 * A + x * B + 2 * x^2 * B + x
又因为B是斐波那契数列的多项式，所以B的闭形式可以直接得到，就是 x/(1-x-x^2) [这个也不难推，可以自己推推]。
于是我们可以开开心心的解出A的闭形式，发现分母是 (1-x-x^2)^2.
然后我们再把 A^3 求出来就可以直接得到答案了， 这个时候分母就是 (1-x-x^2)^6 ，于是我们就可以直接得到一个 A^3 代表的函数的递推式(最好选择让计算机多项式乘法算递推式的系数，不然手算很可能会gg),每一项之和前面的12项有关。 [至于为什么不用考虑分子->因为分子的x的次数和系数只能决定生成函数整体的伸缩和平移，而和递推式没有任何联系，所以可以直接忽略]。
所以现在就可以直接矩阵快速幂了。
。
。
。
。
。
。
。
。
。
是吗？
发现极限数据可能会有 10^5 级别的数据组数，总的复杂度就是 O(10^5 * 12^3 * log(10^18))，然后就凉了。
不过发现M<=100的时候这个数列的循环节特别短，所以可以直接预处理出来然后 M<=100的时候O(1)回答询问。
emmmm,这就做完了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int M,T,NUM[13]={0,6,-9,-10,30,6,-41,-6,30,10,-9,-6,-1};
int f[233],F[233],A[12],B[12];
int ans[105][100005],C[13],len[105];
inline int add(int x,int y,const int ha){
x+=y;
return x>=ha?x-ha:x;
}
struct node{
int a[12][12];
inline void clear(){ memset(a,0,sizeof(a));}
inline void BASE(){ clear(); for(int i=0;i<12;i++) a[i][i]=1;}
node operator *(const node &u)const{
node r; r.clear();
for(int k=0;k<12;k++)
for(int i=0;i<12;i++)
for(int j=0;j<12;j++) r.a[i][j]=add(r.a[i][j],a[i][k]*(ll)u.a[k][j]%M,M);
return r;
}
}ANS,X;
ll N,ci[66];inline void init(){
ci[0]=1;
for(int i=1;i<=60;i++) ci[i]=ci[i-1]+ci[i-1];f[1]=f[2]=1;
for(int i=3;i<=12;i++) f[i]=f[i-1]+f[i-2];
for(int i=1;i<=12;i++)
for(int j=1;i+j<=12;j++)
for(int l=1;l+i+j<=12;l++) F[i+j+l]+=f[i]*f[j]*f[l]*i*j*l;for(M=2;M<=100;M++){
for(int i=1;i<=12;i++) C[i]=add(NUM[i]%M,M,M),ans[M][i]=add(F[i]%M,M,M);
for(int i=13;i;i++){
for(int j=1;j<=12;j++) ans[M][i]=add(ans[M][i],C[j]*(ll)ans[M][i-j]%M,M);
bool flag=1;
for(int j=1;j<=12;j++) if(ans[M][j]!=ans[M][i+j-12]){
flag=0;
break;
}if(flag){
len[M]=i-12;
break;
}
}
}
}inline void solve(){
scanf("%d%lld",&M,&N);
if(M==1) puts("0");
else if(N<=12) printf("%d\n",add(F[N]%M,M,M)*6ll%M);
else if(M<=100) printf("%d\n",ans[M][(N-1)%len[M]+1]*6ll%M);
else{
X.clear(),ANS.BASE(),N-=12;
for(int i=0;i<11;i++) X.a[i][i+1]=1;
for(int i=0;i<12;i++) X.a[i][0]=add(NUM[i+1]%M,M,M);
for(;N;N>>=1,X=X*X) if(N&1) ANS=ANS*X;for(int i=0;i<12;i++) A[i]=add(F[12-i]%M,M,M);
memset(B,0,sizeof(B));
for(int j=0;j<12;j++)
for(int l=0;l<12;l++) B[l]=add(B[l],A[j]*(ll)ANS.a[j][l]%M,M);
printf("%d\n",B[0]*6ll%M);
}
}int main(){
//freopen("sigfib.in","r",stdin);
//freopen("sigfib.out","w",stdout);
init();
scanf("%d",&T);
while(T--) solve();
return 0;
}
