记录编号	74919	评测结果	AAAAAAAAAA
题目名称	1426.eins	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	4.806 s
提交时间	2013-10-26 18:19:18	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll SIZEN=3;
ll MOD;
class MATRIX{
public:
	ll n,m;//n行m列
	ll s[SIZEN][SIZEN];
};
MATRIX operator * (MATRIX &a,MATRIX &b){
	MATRIX c;
	c.n=a.n;c.m=b.m;
	ll i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			c.s[i][j]=0;
			for(k=1;k<=a.m;k++){
				c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
			}
			c.s[i][j]%=MOD;
		}
	}
	return c;
}
MATRIX I;//单位矩阵
MATRIX FO;
MATRIX ori;
MATRIX quickpow(MATRIX a,ll x){//a^x
	MATRIX s;
	s=I;
	while(x){
		if(x&1) s=s*a;
		a=a*a;
		x>>=1;
	}
	return s;
}
ll N;
void init(void){
	I.n=I.m=2;
	I.s[1][1]=1,I.s[1][2]=0;
	I.s[2][1]=0,I.s[2][2]=1;
	FO.n=FO.m=2;
	FO.s[1][1]=0,FO.s[1][2]=1;
	FO.s[2][1]=1,FO.s[2][2]=1;
	ori.n=1,ori.m=2;
	ori.s[1][1]=0,ori.s[1][2]=1;
}
void work(void){
	scanf("%lld%lld",&N,&MOD);
	MATRIX ans;
	MATRIX temp=quickpow(FO,N);
	ans=ori*temp;
	printf("%lld\n",ans.s[1][1]);
}
int main(){
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	init();
	ll i,T;
	scanf("%lld",&T);
	for(i=1;i<=T;i++) work();
	return 0;
}