#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,k,p;
ll n;
vector<int> frac;
inline int qpow(int base,int d) {
	int ans=1;
	while(d) {
		if(d&1) ans=1ll*ans*base%p;
		base=1ll*base*base%p,d>>=1;
	}
	return ans;
}
inline int check_gen(const int v) {
	ffor(i,0,(int)frac.size()-1) if(qpow(v,(p-1)/frac[i])==1) return 0;
	return 1;
}
int calc_gen(void) {
	ffor(i,2,p) if(check_gen(i)) return i;	
}
struct Matrix {int v[2][2];};
Matrix operator *(Matrix A,Matrix B) {
	Matrix C; memset(C.v,0,sizeof(C.v));
	ffor(i,0,1) ffor(j,0,1) ffor(k,0,1) C.v[i][k]=(C.v[i][k]+1ll*A.v[i][j]*B.v[j][k])%p;
	return C;	
}
Matrix operator ^(Matrix A,ll n) {
	Matrix C; C.v[0][0]=C.v[1][1]=1,C.v[0][1]=C.v[1][0]=0;
	while(n) {
		if(n&1) C=C*A;
		A=A*A,n>>=1;
	}
	return C;
}
signed main() {
	ios::sync_with_stdio(False),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n>>k>>p,frac.clear();
		int v=p-1;
		ffor(i,2,v/i) if(v%i==0) {
			frac.push_back(i);
			while(v%i==0) v/=i;	
		}
		if(v>1) frac.push_back(v);
		int ans=0,g=calc_gen(),w=qpow(g,(p-1)/k);
		ffor(j,0,k-1) {
			Matrix mt;
			mt.v[0][0]=mt.v[0][1]=mt.v[1][0]=qpow(w,j),mt.v[1][1]=0;
			mt.v[0][0]++,mt.v[1][1]++;
			mt=mt^n;
			ans=(ans+mt.v[0][0])%p;
		}
		ans=1ll*ans*qpow(k,p-2)%p;
		cout<<ans<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,k,p;
ll n;
vector<int> frac;
inline int qpow(int base,int d) {
	int ans=1;
	while(d) {
		if(d&1) ans=1ll*ans*base%p;
		base=1ll*base*base%p,d>>=1;
	}
	return ans;
}
inline int check_gen(const int v) {
	ffor(i,0,(int)frac.size()-1) if(qpow(v,(p-1)/frac[i])==1) return 0;
	return 1;
}
int calc_gen(void) {
	ffor(i,2,p) if(check_gen(i)) return i;	
}
struct Matrix {int v[2][2];};
Matrix operator *(Matrix A,Matrix B) {
	Matrix C; memset(C.v,0,sizeof(C.v));
	ffor(i,0,1) ffor(j,0,1) ffor(k,0,1) C.v[i][k]=(C.v[i][k]+1ll*A.v[i][j]*B.v[j][k])%p;
	return C;	
}
Matrix operator ^(Matrix A,ll n) {
	Matrix C; C.v[0][0]=C.v[1][1]=1,C.v[0][1]=C.v[1][0]=0;
	while(n) {
		if(n&1) C=C*A;
		A=A*A,n>>=1;
	}
	return C;
}
signed main() {
	ios::sync_with_stdio(False),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n>>k>>p,frac.clear();
		int v=p-1;
		ffor(i,2,v/i) if(v%i==0) {
			frac.push_back(i);
			while(v%i==0) v/=i;	
		}
		if(v>1) frac.push_back(v);
		int ans=0,g=calc_gen(),w=qpow(g,(p-1)/k);
		ffor(j,0,k-1) {
			Matrix mt;
			mt.v[0][0]=mt.v[0][1]=mt.v[1][0]=qpow(w,j),mt.v[1][1]=0;
			mt.v[0][0]++,mt.v[1][1]++;
			mt=mt^n;
			ans=(ans+mt.v[0][0])%p;
		}
		ans=1ll*ans*qpow(k,p-2)%p;
		cout<<ans<<'\n';
	}
	return 0;
}