#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
unsigned long long t,n,p;
int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>t;
	while (t--)
	{
		cin>>n>>p;
if (n==0)
cout<<"0\n";
else if (n==1)
cout<<"1\n";
		else
		{
			int a,b,c;
			 a=0; 
			  b=1;
			    for(int i=2; i<=n; i++)
			  {
				c=(a+b)%p;
				a=b; 
				b=c;
}
			cout<<c;
}
}

	return 0;
}