求解: 幂塔函数: $$ a^{a^{a^{a^{}…}}} $$ 或另一种幂塔函数: $$ a^{b^{c^{d^{…}}}} $$ $\\phi(x)$是欧拉函数 欧拉降幂: $$ a^{b} \\equiv\\left{\\begin{array}{ll}a^{b % \\phi(p)} & g c d(a, p)=1 \\a^{b} & g c d(a, p) \\neq 1, b<\\phi(p) \\a^{b % \\phi(p)+\\phi(p)} & g c d(a, p)\\neq 1, b \\geq \\phi(p)\\end{array} \\quad(\\bmod p)\\right. $$ code模板: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using ll = long long;
using namespace std;

#define MOD(a,b) a>=b?a%b+b:a  //重定义取模，按照欧拉定理的条件
const int maxn = 1e6 + 10;

map<int, int> ma;
ll w[maxn], m, r, x;

ll qpow(ll a, ll b, ll mod) { //快速幂
    ll res = 1;
    while (b) {
        if (b & 1) res = MOD(res * a, mod);
        a = MOD(a * a, mod);
        b >>= 1;
    }
    return res;
}

ll getphi(ll x) {  //求互质个数
    ll ans = x;
    if (ma.count(x)) return ma[x];
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1) ans = ans / x * (x - 1); //*****
    ma[x] = ans;
    return ans;
}
ll solve(int ceng, ll mod) { //每层的幂是w[i]
    if (ceng == r || mod == 1)
        return MOD(w[ceng], mod);
    return
        qpow(w[ceng], solve(ceng + 1, getphi(mod)), mod);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        //scanf("%lld %lld %lld", &x, &r, &m);
        scanf("%lld %lld", &r, &m);
        if (!r) {
            cout << 1 % m << endl;
            continue;
        }
        //for (int i = 1; i <= r; i++) // 这个地方如果求幂塔函数(a^a^a^a^...)就这样写, 如果求a^b^c^d^...就自己输入w[i] 
            //w[i] = x;
        for (int i = 1; i <= r; i++)
            scanf("%lld", &w[i]);
        printf("%lld\n", solve(1, m) % m);
    }
    return 0;
}