#include <stdio.h>
#define N 2
#define fre freopen("eins.in","r",stdin);freopen("eins.out","w",stdout);
#define fcl fclose(stdin);fclose(stdout);
char ch;void _read(unsigned long long &xx){while(ch=getchar(),ch<48||ch>58);xx=ch-48;while(ch=getchar(),ch>47&&ch<59)xx=xx*10+ch-48;}
unsigned long long m;
unsigned long long _add(unsigned long long a,unsigned long long b){return (a+b)%m;}
unsigned long long _mul(unsigned long long a,unsigned long long b){return (a*b)%m;}
struct _rabit{
	unsigned long long a[N][N];
	_rabit(){a[1][1]=a[1][0]=a[0][1]=a[0][0]=0;}
	_rabit operator * (const _rabit &x)const{
		_rabit ans;
		for(int j,k,i=0;i<N;i++)
		for(j=0;j<N;j++)
		for(k=0;k<N;k++)
			ans.a[i][j]=_add(ans.a[i][j],_mul(a[i][k],x.a[k][j]));
		return ans;
	}
};
_rabit _pow(_rabit x,unsigned long long k){
	_rabit ans;ans.a[1][1]=ans.a[0][0]=1;
	while(k){
		if(k&1)ans=ans*x;
		x=x*x;k>>=1;
	}
	return ans;
}
unsigned long long _run(unsigned long long n){
	_rabit ans,x;ans.a[0][1]=1;
	x.a[0][0]=x.a[0][1]=x.a[1][0]=1;
	x=_pow(x,n);ans=ans*x;
	return ans.a[0][0]%m;
}
void _run(){
	unsigned long long t,ans,n;_read(t);
	while(t--){
		_read(n),_read(m);
		ans=_run(n);
		printf("%llu\n",ans);
	}
}
bool _Rabit(),_RABIT=_Rabit();int main(){;}
bool _Rabit(){
//#define _carrot
#ifndef _carrot
	fre
#endif 
	_run();
#ifndef _carrot
	fcl
#endif
#ifdef _carrot
	getchar(),getchar(),getchar();
#endif
}