#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<ctime>
#define ll long long
#define N 10003
#define M 180
#define mid ((l+r)>>1)
using namespace std;

int siz,p;

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
    	t >>= 1;
    }
    return res;
}
/*
namespace Berlekamp_Massey{
    inline void add(int &x,int y){
        x += y;
        if(x>=p) x -= p;
    }

    inline void dec(int &x,int y){
        x -= y;
        if(x<0) x += p;
    }

    int cnt;
    int Fail[N],delta[N];
    vector<int> R[N];

    int solve(int n,const int *a,int *f){
		int k = 0;
        memset(Fail,0,sizeof(Fail));
        memset(delta,0,sizeof(delta));
        R[0].clear();
        cnt = 0;
        for(int i=1;i<=n;++i){
            if(cnt==0){
                if(a[i]){
                    Fail[cnt++] = i;
                    delta[i] = a[i];
                    R[cnt].resize(0);
                    R[cnt].resize(i,0);
                }
                continue;
            }
            int sum = 0,m = R[cnt].size();
            delta[i] = a[i];
            Fail[cnt] = i;
            for(int j=0;j<m;++j)
                sum = (sum+(ll)a[i-j-1]*R[cnt][j])%p;
            dec(delta[i],sum);    
            if (!delta[i]) continue;
            int id = cnt-1,v = i-Fail[id]+(int)R[id].size();
            for(int j=0;j<cnt;++j){
                if(i-Fail[j]+(int)R[j].size()<v){
                    id = j;
                    v = i-Fail[j]+(int)R[j].size();
                }
            }
            int tmp = (ll)delta[i]*power(delta[Fail[id]],p-2)%p;
            R[cnt+1] = R[cnt];
            while(R[cnt+1].size()<v) R[cnt+1].push_back(0);
            add(R[cnt+1][i-Fail[id]-1],tmp);
            for(int j=0;j<R[id].size();++j)
                dec(R[cnt+1][i-Fail[id]+j],(ll)tmp*R[id][j]%p);
            cnt++;
        }
        k = R[cnt].size();
        for(int i=1;i<=k;++i) f[i] = R[cnt][i-1];
		return k;
    }
}
*/
inline int add(const int& x,const int& y){ return x+y>=p?x+y-p:x+y; }
inline int dec(const int& x,const int& y){ return x<y?x-y+p:x-y; }

inline void mod(const int *f,const int *g,int n,int m,int *R){
	static int a[N],b[N],q[N];
	memcpy(a,f,(n+1)<<2),memcpy(b,g,(m+1)<<2);
	for(int i=n-m;~i;--i){
		q[i] = a[i+m];
		for(int j=0;j<=m;++j) 
			a[m+i-j] = (a[m+i-j]-(ll)q[i]*b[m-j])%p;
	}
	for(int i=0;i<m;++i) R[i] = a[i];
}

inline void multiply(const int *f,const int *g,int n,int m,int *r){
	static int h[N];
	memset(h,0,(n+m+1)<<2);
	for(int i=0;i<=n;++i)
	for(int j=0;j<=m;++j)
		h[i+j] = (h[i+j]+(ll)f[i]*g[j])%p;
	memcpy(r,h,(n+m+1)<<2);
}

struct complex{ 
    int a,b;
    complex(int a=0,int b=0):a(a),b(b){}

    complex operator + (const complex& x) const{
        return complex((a+x.a)%p,(b+x.b)%p);
    }
    complex operator - (const complex& x) const{
        return complex((a-x.a)%p,(b-x.b)%p);
    }
    complex operator * (const complex& x) const{
        complex res;
        return complex(((ll)a*x.a+5ll*b*x.b)%p,((ll)a*x.b+(ll)b*x.a)%p);
    }
};

inline complex power(complex a,ll t){
    complex res = complex(1,0); 
    while(t){
        if(t&1) res = res*a;
        a = a*a;
        t >>= 1;
    }
    return res;
}

inline int fib(ll n){
	if(p==2) return n%3!=0;
	int inv2 = (p+1)>>1;
	complex x = complex(inv2,inv2);
	complex y = complex(inv2,p-inv2);
	complex res = power(x,n)-power(y,n);
	return (res.b+p)%p;
}

int n,ans,lim;
ll m;
int B[36][36],D[36][36],F[M][36][36];
int g[M],cf[M];
int a[M],b[M],res[M];
int dc[36][36];

int main(){
	int T,k;
	scanf("%d",&T);
	while(T--){
		scanf("%d%lld%d",&n,&m,&p);
		if((n&1)&(m&1)){
			puts("0");
			continue;
		}
		if(n==1){
			puts("1");
			continue;
		}
		if(n==2){
			printf("%d\n",fib(m+1));
			continue;
		}
		//printf("n = %d,m = %lld\n",n,m);
		for(int i=0;i<=n;++i) dc[0][i] = 1;
		for(int i=1;i<=n;++i){
			dc[i][0] = 1;
			for(int j=1;j<=n;++j)
				dc[i][j] = ((dc[i-1][j]+dc[i][j-1])%p+dc[i-1][j-1])%p;
		}
		siz = n,lim = (n<<1)+2;		
		memset(F[0],0,sizeof(F[0]));
		memset(F[1],0,sizeof(F[1]));
		for(int i=0;i<n;++i) F[0][i][i] = 1;
		for(int i=0;i<(n-1);++i){
			F[1][i][i+1] = 1;
			F[1][i+1][i] = p-1;
		}
		for(int i=2;i<=lim;++i){
			for(int j=0;j<n;++j)
			for(int k=0;k<n;++k){
				F[i][j][k] = p-F[i-2][j][k];
				if(k-1>=0) F[i][j][k] = add(F[i][j][k],F[i-1][j][k-1]);
				if(k+1<n) F[i][j][k] = dec(F[i][j][k],F[i-1][j][k+1]);
			}
		}
		for(int i=0;i<n;++i) cf[i+1] = -dc[i][n-i];
		reverse(cf+1,cf+n+1);
		memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
		memset(res,0,sizeof(res));
		//memset(a,0,(n+1)<<3),memset(b,0,(n+1)<<3);
		//memset(res,0,(n+1)<<3);
		for(int i=1;i<=n;++i) a[n-i] = p-cf[i];
		a[n] = b[1] = res[0] = 1;
		int bt = 1,rt = 0,tn = n;
		ll tm = m;
		m >>= 1;
		while(1){
			if(m&1){
				multiply(res,b,rt,bt,res);
				rt += bt;
				if(rt>=n) mod(res,a,rt,n,res);
				rt = min(rt,n-1);
			}
			m >>= 1;
			if(m==0) break;
			multiply(b,b,bt,bt,b);
			bt <<= 1;
			if(bt>=n) mod(b,a,bt<<1,n,b);
			bt = min(bt,n-1);
		}
		//for(int i=0;i<n;++i) printf("%d ",res[i]);
		//putchar('\n');
		memset(D,0,sizeof(D));
		memset(B,0,sizeof(B));
		
		for(int i=0;i<(n<<1);++i){
			if((tm&1)!=(i&1)) continue;
			for(int t=0;t<n;++t)
			for(int j=0;j<n;++j)
				D[t][j] = (D[t][j]+(ll)res[i>>1]*F[i][t][j])%p;
		}
		for(int i=0;i<n;++i){
			if((i&1)==0) continue;
			for(int j=0;j<n;++j){
				if(D[i][j]==0) continue;
				B[i>>1][j>>1] = D[i][j];
			}
		}
		n >>= 1;
		int d,flag = 1;
		for(int i=0;i<n;++i){
			int j = i;
			while(j<n&&B[j][i]==0) ++j;
			if(j==n) continue;
			if(j!=i){
				for(int k=i;k<n;++k) swap(B[i][k],B[j][k]);
				flag ^= 1;
			}
			for(j=i+1;j<n;++j){
				if(B[j][i]==0) continue;
				d = (ll)B[j][i]*power(B[i][i],p-2)%p;
				for(int k=i;k<n;++k) B[j][k] = (B[j][k]-(ll)d*B[i][k])%p;
			}
		}
		ans = 1;
		for(int i=0;i<n;++i) ans = (ll)ans*B[i][i]%p;
		if(tn%4==2||tn%4==3) ans = ((tm-1)>>1)&1?ans:-ans;
		if(flag==0) ans = p-ans;
		ans = (ans%p+p)%p;
		printf("%d\n",ans);
	}
	return 0;
}