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

int t,n,p;

int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d",&n,&p);
		if (n==0)
			printf("0\n");
		else if (n==1)
			printf("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;
			}
			printf("%d\n",c);
		}
	}

	return 0;
}