#include <bits/stdc++.h>
#define NAME "repnum"
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i,a ,b) for(int i = (a), _b = (b); i >= _b; --i)
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int maxN = 30;
const int maxK = 1e5 + 10;
int t, n;
ll m, k;
ll a[maxN];
ll ans;
ll f[maxN][maxN][maxK];
void io()
{
	freopen(NAME".inp", "r", stdin);
	freopen(NAME".out", "w", stdout);
}
struct P
{
	ll t[maxN][maxN];
	init() {
		FOR(i, 1, n + 1) FOR(j, 1, n + 1) t[i][j] = 0;
	};
};
P F, G;
P nhan(P A, P B)
{
	P C;
	C.init();
	FOR(i, 1, 1)
	{
		FOR(j, 1, n)
		{
			FOR(k, 1, n)
			{
				C.t[i][j] = (C.t[i][j]%m + (A.t[i][k]%m * B.t[k][j]%m) %m) % m ;
			}
		}
	}
	return C;
}
void proc()
{
	ans = 0;
	FOR(i, 1, n)
	{
		FOR(j, 1, n) if (__gcd(a[i], a[j]) == 1) F.t[i][j] = 1;
		else F.t[i][j] = 0;
	}
	G = F;
	ans = F.t[1][n] % m;
	FOR(i, 2, k)
	{
		G = nhan(G, F);
		ans = (ans % m + G.t[1][n] % m) % m;
	}
	printf("%lld\n", ans);
}
int main()
{
	//io();
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %lld %lld", &n, &k, &m);
		FOR(i, 1, n) scanf("%lld", &a[i]);
		proc();
	}
	return 0;
}
/*
4

4 4 1000
2 4 3 5

4 4 1000
2 4 3 5

4 100 1000
2 4 3 5

4 2 1000
2 4 3 5
*/