#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cctype> 
using namespace std;
int tempA,tempB,tempC,tempD;
template<typename T>inline T read(T &x)
{
	int f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
	if(ch=='-')
	f=-1;
	for(x=0;isdigit(ch);ch=getchar())
	x=10*x+ch-'0';
	return x*=f;
}
template<typename T>inline void write(T x)
{
	if(x==0)
	{
		putchar('0');
		return ;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	int top=0;
	static char s[20];
	for(;x;x/=10)
	s[++top]=x%10+'0';
	while(top)
	{
		putchar(s[top--]);
	}
	return ;
}
void func(int n,int &a,int &b,int &c,int &d,int p){
    if(n==1){
        a=0;
        b=c=d=1;
        return ;
    }
    if(n%2==0){
        func(n/2,a,b,c,d,p);
        tempA=a*a+b*c;
        tempB=b*(a+d);
        tempC=c*(a+d);
        tempD=c*b+d*d;
        a=tempA%p;
        b=tempB%p;
        c=tempC%p;
        d=tempD%p;
        return;
    }
    else{
        func(n/2,a,b,c,d,p);
        tempA=b*(a+d);
        tempB=a*a+b*(a+c+d);
        tempC=c*b+d*d;
        tempD=c*(a+b+d)+d*d;
        a=tempA%p;
        b=tempB%p;
        c=tempC%p;
        d=tempD%p;
        return;
    }
}
int main()
{
	ios::sync_with_stdio(false);
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
    int n,p,t;
    read(t);
    for(int i=1;i<=t;++i)
    {
    	read(n);
    	read(p);
    	if(n==0)
    	{
    		continue;
    	}
        if(n<=2)
		{
            cout<<1<<endl;
            continue;
        }
        else n-=2;
        int a,b,c,d;
        func(n,a,b,c,d,p);
        cout<<(b+d)%p<<endl;
    }   
	fclose(stdin);
	fclose(stdout); 
    return 0;
}