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

int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	int t;
	cin>>t;
	long long n,p;
	int f0,f1,f2;
	f0=0;f1=1;
	for(int i=1;i<=t;i++)
	{
		cin>>n>>p;
		for(int j=1;j<n;j++)
		{
			f2=f1+f0;
			f0=f1;
			f1=f2;
		}
		f2%=p;
		cout<<f2<<endl;
		f0=0;f1=1;
	} 
	return 0;
}