#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long int LL;
typedef vector<int> VI;

#define sd(x) scanf("%d", &x)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 2000000000
#define MOD 1000000007
#define D double
#define LD long double

inline int lcm(int a, int b){
    return (a * b) / __gcd(a, b);
}

int PowerMod(int a, int p, int mod){
    int ret = 1;
    a %= mod;
    while(p > 0){
        if(p & 1){
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return ret;
}

#define M 5123
#define N 112345
#define P 1123456

int nxt[M];
bool isp[P];
bool contains[M][M];
int other[M][M];

inline void pre(){
    int i, j, k, l;
    for(i = 3; i < P; i += 2){
        isp[i] = true;
    }
    isp[2] = true;
    for(i = 3; i * i < P; ++i){
        if(isp[i] == true){
            for(j = i * i; j < P; j += i){
                isp[j] = false;
            }
        }
    }
    for(i = 1; i < M; ++i){
        nxt[i] = 1;
    }
    for(i = 2; i < M; ++i){
        for(j = 2; j < M; ++j){
            if(isp[j] == true && i % j == 0){
                k = i;
                while(k % j == 0){
                    k /= j;
                }
                l = i / k;
                contains[i][j] = true;
                other[i][j] = k;
                if(nxt[i] == 1){
                    nxt[i] = lcm(nxt[k], (l / j) * (j - 1));
                }
            }
        }
    }
}

int n, t, m, tt;
int a[N];
int cnt[2][M];
int ca[N];

inline void go(int f, int l, int mod){
    //cout<<l<<" "<<mod<<endl;
    int len = l;
    int i;
    int j, k, ipl;
    if(l == 1){
        for(i = 0; i < mod; ++i){
            cnt[f][i] = 0;
        }
        for(i = 0; i < n; i++){
            j = a[i] % mod;
            cnt[f][j]++;
            if(cnt[f][j] >= m){
                cnt[f][j] -= m;
            }
        }
        return;
    }
    if(mod == 1){
        for(i = 0; i < mod; ++i){
            cnt[f][i] = 0;
        }
        cnt[f][0] = PowerMod(n, l, m);
        return;
    }
    if(mod == 2){
        for(i = 0; i < mod; ++i){
            cnt[f][i] = 0;
        }
        cnt[f][1] = PowerMod(n, l, m);
        return;
    }
    int new_mod = nxt[mod];
    go(1 - f, l - 1, new_mod);
    for(i = 0; i < mod; ++i){
        cnt[f][i] = 0;
    }
    for(i = 0; i < mod; ++i){
        ca[i] = 0;
    }
    for(i = 0; i < n; ++i){
        j = a[i] % mod;
        ca[j]++;
        if(ca[j] >= m){
            ca[j] -= m;
        }
    }
    cnt[f][0] = (ca[0] * PowerMod(n, l - 1, mod)) % mod;
    for(i = 1; i < mod; ++i){
        if(ca[i] > 0){
            if(contains[mod][i] == true){
                j = other[mod][i];
                k = mod / j;
                k = (k * PowerMod(k, nxt[j] - 1, j)) % mod;
                ipl = 1;
                for(l = 0; l < new_mod; l++){
                    if(cnt[1-f][l] > 0){
                        cnt[f][(ipl * k) % mod] += (cnt[1-f][l] * ca[i]) % m;
                    }
                    ipl *= i;
                    ipl %= j;
                }
            }
            else{
                ipl = 1;
                for(l = 0; l < new_mod; l++){
                    if(cnt[1-f][l] > 0){
                        cnt[f][ipl] += (cnt[1-f][l] * ca[i]) % m;
                    }
                    ipl *= i;
                    ipl %= mod;
                }
            }
        }
    }
    for(i = 0; i < mod; ++i){
        cnt[f][i] %= m;
    }
}

inline void solve(){
    int i, ans = 0;
    sd(n); sd(m);
    if(tt > 1){
        assert(2 <= m && m <= 500);
        assert(2 <= n && n <= 100);
    }
    else{
        assert(2 <= n && n <= 100000);
        assert(2 <= m && m <= 5000);
    }
    for(i = 0; i < n; ++i){
        sd(a[i]);
        assert(4 < a[i] && a[i] < 1000000);
        assert(isp[a[i]]);
    }
    go(0, n, m);
    for(i = 0; i < m; ++i){
        ans += (i * cnt[0][i]);
        ans %= m;
    }
    cout<<ans<<endl;
}

int main(){
    //freopen("1.txt", "r", stdin);
    pre();
    sd(t);
    tt = t;
    assert(1 <= t && t <= 1000);
    while(t--){
        solve();
    }
	return 0;
}