#include<bits/stdc++.h>
using namespace std;
long long n,fn,p;
struct XTT
{
	long long x1,x2,y1,y2;
};
XTT operator *(XTT const &a,XTT const &b)
{
	XTT ans;
	ans.x1=a.x1*b.x1+a.x2*b.y1,ans.x1%=p;
	ans.x2=a.x1*b.x2+a.x2*b.y2,ans.x2%=p;
	ans.y1=a.y1*b.x1+a.y2*b.y1,ans.y1%=p;
	ans.y2=a.y1*b.x2+a.y2*b.y2,ans.y2%=p;
	return ans;
}
XTT POW(XTT const &x,int const &y)
{
	if(y<=1)
		return x;
	if(y%2==0)
		return POW(x*x,y/2);
	return POW(x*x,y/2)*x;
}
int main()
{
	
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	XTT b={1,0,0,0}; 
	XTT f={1,1,1,0};
	cin>>n;
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&fn,&p);
		if(fn==0)
			cout<<0<<endl;
		else
		{
			printf("%d\n",((b*POW(f,fn-1)).x1)%p);
		}
	}
	return 0;
}