|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e5 + 10;
|
|
|
|
|
|
#define int long long
|
|
|
|
|
|
#define endl '\n'
|
|
|
|
|
|
|
|
|
|
|
|
// 快速幂
|
|
|
|
|
|
int qmi(int a, int b, int p) {
|
|
|
|
|
|
int res = 1;
|
|
|
|
|
|
while (b) {
|
|
|
|
|
|
if (b & 1) res = res * a % p;
|
|
|
|
|
|
b >>= 1;
|
|
|
|
|
|
a = a * a % p;
|
|
|
|
|
|
}
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 求单个数的欧拉函数值
|
|
|
|
|
|
int phi(int x) {
|
|
|
|
|
|
int res = x;
|
|
|
|
|
|
for (int i = 2; i <= x / i; i++)
|
|
|
|
|
|
if (x % i == 0) {
|
|
|
|
|
|
res = res / i * (i - 1);
|
|
|
|
|
|
while (x % i == 0) x /= i;
|
|
|
|
|
|
}
|
|
|
|
|
|
if (x > 1) res = res / x * (x - 1);
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 判断n层幂塔指数是否>=phi
|
|
|
|
|
|
bool check(int a, int n, int phi) {
|
|
|
|
|
|
if (n == 0) return phi <= 1; // 0层幂塔是1
|
|
|
|
|
|
if (a >= phi) return true; // 底数a>=phi，那么它的幂塔一定>=phi
|
|
|
|
|
|
return check(a, n - 1, log(phi) / log(a)); // 取对数，消去一层，继续判断
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 计算n层幂塔: a^a^a^a..^a (mod m)
|
|
|
|
|
|
// 其中共有n个a
|
|
|
|
|
|
int f(int a, int n, int m) {
|
|
|
|
|
|
if (m == 1) return 0; // 对1取模，恒为0
|
|
|
|
|
|
if (n <= 1) return qmi(a, n, m);
|
|
|
|
|
|
int p = phi(m);
|
|
|
|
|
|
// 互质
|
|
|
|
|
|
if (__gcd(a, m) == 1) return qmi(a, f(a, n - 1, p), m);
|
|
|
|
|
|
// 不互质
|
|
|
|
|
|
if (check(a, n - 1, p))
|
|
|
|
|
|
return qmi(a, f(a, n - 1, p) + p, m); // a的指数>=phi
|
|
|
|
|
|
|
|
|
|
|
|
return qmi(a, f(a, n - 1, p), m); // a的指数<phi, 所以改成对phi取模对答案无影响
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
signed main() {
|
|
|
|
|
|
int T;
|
|
|
|
|
|
cin >> T;
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
int a, n, m;
|
|
|
|
|
|
cin >> a >> n >> m;
|
|
|
|
|
|
cout << f(a, n, m) << endl;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
