//AUTHOR::STDAFX
//ALGORITHM::Math

#define MAXN 12UL
 
#include <cstdio>
#include <cstring>
 
int Mod;
 
struct Martix{
    int 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);	
    int t,input;
    scanf("%d",&t);
    for(int b=0;b<t;b++){
    	scanf("%d%d",&input,&Mod);
    	if(input==0){
    		printf("0\n");
		}
		else if(input==1){
			printf("1\n");
		}
		else{
			int 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("%d\n",f.data[1][1]%Mod);
		}
	}
    return 0;
}