#include
using namespace std;
typedef long long dint;
#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif
#define _l (long long int)
#define mInc(a,b) {
a += b;
if (a >= mod)
a -= mod;
}
const int maxn = 40009;
dint n; int k, mod;
struct matrix { static const int n = 2; int a[n][n]; matrix() {} void init() { memset(a, 0, sizeof(a)); } void setOne() { memset(a, 0, sizeof(a)); for (int i = 0; i < n; ++ i) a[i][i] = 1; } void operator =(const matrix& b) { memcpy(a, b. a, sizeof(a)); } void mul(int b) { for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) a[i][j] = _l a[i][j] * b % mod; } void mul(const matrix& b) { static int s[n][n]; memset(s, 0, sizeof(s)); for (int k = 0; k < n; ++ k) for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) s[i][j] = (s[i][j] + _l a[i][k] * b. a[k][j]) % mod; memcpy(a, s, sizeof(a)); } void add(const matrix& b) { for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) mInc(a[i][j], b. a[i][j]); } };
int modPow(int a, dint x) { int s(1); for (; x; x »= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; }
int findRoot() { static int fac[maxn]; int tfac(0); for (int i = 1, v = mod - 1; i * i <= v; ++ i) if (v % i == 0) { fac[tfac ++] = i; if (i > 1 && i * i < v) fac[tfac ++] = v / i; } for (int i = 1; 1; ++ i) { bool f(1); for (int j = 0; j < tfac && f; ++ j) if (modPow(i, fac[j]) == 1) f = 0; if (f) return i; } }
int sov() { int wo(modPow(findRoot(), (mod - 1) / k)), wi(modPow(wo, mod - 2)); int wf(1), w(1), s(0); matrix a, g; for (int i = 0; i < k; ++ i, w = _l w * wi % mod, wf = _l wf * wo % mod) { a. setOne(); a. mul(w); mInc(a. a[0][0], 1); mInc(a. a[0][1], 1); mInc(a. a[1][0], 1); g. setOne(); for (dint x = n; x; x »= 1, a. mul(a)) if (x & 1) g. mul(a); g. mul(modPow(wf, n)); mInc(s, g. a[0][0]); } return _l s * modPow(k, mod - 2) % mod; }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
int t;
scanf("%d\n", &t);
while (t --) {
scanf(lld "%d%d", &n, &k, &mod);
printf("%d\n", sov());
}
}