#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;
    }
}

struct mat{
	int a[36][36];
	inline mat(){ memset(a,0,sizeof(a)); }
};

inline mat operator * (const mat& lhs,const mat& rhs){
	mat res = mat();
	for(int i=0;i<siz;++i)
	for(int j=0;j<siz;++j)
	for(int k=0;k<siz;++k)
		res.a[i][j] = (res.a[i][j]+(ll)lhs.a[i][k]*rhs.a[k][j])%p;
	return res;
}

inline mat operator * (const int& lhs,const mat& rhs){
	mat res = mat();
	for(int i=0;i<siz;++i)
	for(int j=0;j<siz;++j)
		res.a[i][j] = (ll)lhs*rhs.a[i][j]%p;
	return res;
}

inline mat operator + (const mat& lhs,const mat& rhs){
	mat res;
	for(int i=0;i<siz;++i)
	for(int j=0;j<siz;++j)
		res.a[i][j] = (lhs.a[i][j]+rhs.a[i][j])%p;
	return res;
}

inline mat operator - (const mat& lhs,const mat& rhs){
	mat res;
	for(int i=0;i<siz;++i)
	for(int j=0;j<siz;++j)
		res.a[i][j] = (lhs.a[i][j]-rhs.a[i][j]+p)%p;
	return res;
}

inline mat power(mat a,ll t){
	mat res = mat();
	for(int i=0;i<siz;++i) res.a[i][i] = 1;
	while(t){
		if(t&1) res = res*a;
		t >>= 1;
		if(t==0) break;
		a = a*a;
	}
	return res;
}

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] = (ll)a[i+m]*power(b[m],p-2)%p;
		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){
	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;
		}
		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] = (F[i][j][k]+F[i-1][j][k-1])%p;
				if(k+1<n) F[i][j][k] = (F[i][j][k]-F[i-1][j][k+1]+p)%p;
			}
		}
		k = (n<<1);
		for(int i=1;i<=k;++i){
			int ti = i>>1;
			cf[i] = (i&1)?-dc[ti][n-ti]:0;
		}
		reverse(cf+1,cf+k+1);
		memset(a,0,(k+1)<<3),memset(b,0,(k+1)<<3);
		memset(res,0,(k+1)<<3);
		for(int i=1;i<=k;++i) a[k-i] = p-cf[i];
		a[k] = b[1] = res[0] = 1;
		int bt = 1,rt = 0;
		ll tm = m;
		while(1){
			if(m&1){
				multiply(res,b,rt,bt,res);
				rt += bt;
				if(rt>=k) mod(res,a,rt,k,res);
				rt = min(rt,k-1);
			}
			m >>= 1;
			if(m==0) break;
			multiply(b,b,bt,bt,b);
			bt <<= 1;
			if(bt>=k) mod(b,a,bt<<1,k,b);
			bt = min(bt,k-1);
		}
		memset(D,0,sizeof(D));
		for(int i=0;i<k;++i)
		for(int t=0;t<n;++t)
		for(int j=0;j<n;++j)
			D[t][j] = (D[t][j]+(ll)res[i]*F[i][t][j]%p+p)%p;
		for(int i=0;i<n;++i){
			if((i&1)!=(n&1)) 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;
		for(int i=0;i<n;++i)
		for(int j=i+1;j<n;++j){
			if(B[i][j]==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(((__int128_t)n*tm/2)%2==1) ans = p-ans;
		ans = (ans%p+p)%p;
		printf("%d\n",ans);
	}
	return 0;
}