#include<cstdio>
#include<cstring>
#define LL long long 
using namespace std;
LL A,B,N;
LL MOD;
LL t;
struct MA
{		LL a[3][3];
		void init(LL t)
		{
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<3;j++)
				{
					a[i][j]=0;
				}
			}
			for(int i=0;i<3;i++)a[i][i]=t;
			
		}
		//返回类型MA *位运算符把地址传过来 
		MA operator *(const MA &b)const
		{
			MA c;
			for(int i=1;i<=2;i++)
			{
				for(int j=1;j<=2;j++)
				{
				 c.a[i][j]=0;
				 for(int k=1;k<=2;k++)
				 {
				 	c.a[i][j]+=a[i][k]*b.a[k][j];
				 	c.a[i][j]=c.a[i][j]%MOD;
				 }	
				}
			}
			return c; 
		}
}T;
LL qpow(LL x,LL n)
{
	LL ans=1;
	for(;n;n>>=1,x*=x)if(n&1)ans*=x;
	return ans;
}
MA qpow(MA x,LL n)
{
	MA ans;
	ans.init(1);
	for(;n;n>>=1,x=x*x)
	{
		if(n&1)ans=ans*x;
	}
	return ans;
}
int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	scanf("%lld",&t);
	while(t--)
	{
	scanf("%lld",&N);scanf("%lld",&MOD);
	if(N==0)
	{
		puts("0");
		continue;
	}
	if(N==1||N==2)
	{
		printf("%d\n",1%MOD);
		continue;
	}
	MA p;
	p.init(0);
	p.a[1][1]=1;
	p.a[1][2]=1;
	p.a[2][1]=1;
	MA Ans=qpow(p,N-2);
	printf("%lld\n",(Ans.a[1][1]+Ans.a[1][2])%MOD);
	}
	return 0;
}