记录编号	187471	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	4.022 s
提交时间	2015-09-19 09:28:51	内存使用	0.29 MiB

#define MAXN 4UL
 
#define ll long long
 
#include <cstdio>
#include <cstring>
 
ll Mod;
 
struct Martix{
    ll data[MAXN][MAXN];
    inline void init(){
        clr();
        data[1][1]=0;data[1][2]=1;
        data[2][1]=1;data[2][2]=1;
        return;
    }
    inline void clr(){
        memset(data,0,sizeof(data));
        return;
    }
    friend Martix operator * (Martix a,Martix b){
        Martix temp;
        temp.clr();
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                for(int k=1;k<=2;k++){
                    temp.data[i][j]=(temp.data[i][j]+a.data[i][k]*b.data[k][j])%Mod;
                }
            }
        }
        return temp;
	}
};
 
Martix rs;
 
int main(){
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);	
    ll t,input;
    scanf("%lld",&t);
    for(ll b=0;b<t;b++){
    	scanf("%lld%lld",&input,&Mod);
    	if(input==0){
    		printf("0\n");
		}
		else if(input==1){
			printf("%d\n",1%Mod);
		}
		else{
			ll k=input-1;
			Martix ans,rs,f,cs;
		    rs.data[1][1]=1;
		    rs.data[1][2]=1;
		    rs.data[2][1]=2;
		    rs.data[2][2]=3;
			cs.init();
		    ans.data[1][1]=1;
		    ans.data[1][2]=0;
		    ans.data[2][1]=0;
		    ans.data[2][2]=1;
			while(k){
				if(k&1){
					ans=ans*cs;
				}
				k>>=1;
				cs=cs*cs;
			}
			f=rs*ans;
			printf("%lld\n",f.data[1][1]%Mod);
		}
	}
    return 0;
}