#include<cstring>
using namespace std;
int i,j,n,t,p;
struct {
	long long a[3][3];
	matrix(){
		memset(a,0,sizeof a);
	}
	void operator *=(const matrix &x){
		matrix ans=matrix();
		for (int i=1;i<=2;i++)
			for (int j=1;j<=2;j++)
			ans.a[i][j]=(a[i][1]*x.a[1][j]+a[i][2]*x.a[2][j])%p;
		*this=ans;
	}
	void clear(){
		a[1][1]=a[1][2]=a[2][1]=1%p;	a[2][2]=0;
	}
}x=matrix(),ans=matrix();
void work(){
	while (n){
		if (n&1)	ans*=x;
		x*=x;	n/=2;
	}
}
int main(){
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n,&p);
		if (n==0)	{printf("0n");	continue;}
		ans.clear();	x.clear();	n--;	work();
		printf("%lldn",ans.a[2][1]);
	}
	return 0;
}