#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

//const int maxn=1000000000+1;
int t,n,p;
//char a[maxn];
int a,b,s;
int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	
	cin>>t;
//	a[0]=0; a[1]=1;

	for (int i=1; i<=t; i++)
	{
		a=1;b=0;
		cin>>n>>p;
	//	for (int j=2; j<=n; j++)
	//	{
	//		a[j]=(a[j-1]%p+a[j-2]%p)%p;
	//	}
	//	cout<<a[n]<<endl;
		for (int j=1; j<n; j++)
		{
			s=(a%p+b%p)%p;
			b=a;a=s;	
		}
		cout<<s<<endl;
	}
	return 0;
}