#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long int ll;

#define mp	make_pair
#define pb push_back
#define ModMax 5000
#define NMax 100000

int mod_period[ModMax+1],traversed[ModMax+1],InputArray[NMax+1];

vector<pair<pair<int,int>,int> > PreModulo_Factorization[ModMax+1];

void Experiment()
{
	int maxi = 0;
	for(int i=1;i<=ModMax;i++){
		int sum = 0;
		int M = i;
		sum += (M*mod_period[M]);
		while(M != 1){
			M = mod_period[M];
			sum += (M*mod_period[M]);	
		}
		maxi = max(maxi,sum);
	}
	printf("%d\n",maxi);
}

int Inverse(int a,int b)					//b>a
{
	int Remainder,p0=0,p1=1,pcurr=1,q,m=b;
	while(a!=0)
	{
		Remainder=b%a;
		q=b/a;
		if(Remainder!=0)
		{
			pcurr=p0-(p1*q)%m;
			if(pcurr<0)
				pcurr+=m;
			p0=p1;
			p1=pcurr;
		}
		b=a;
		a=Remainder;
	}
	return pcurr;
}

int powermod(int A,int B,int M)
{
	int result = 1;
	while(B){
		if ( B&1 ){
			result = result*A;
			result %= M;
			B--;
		}
		else{
			A = A*A;
			A %= M;
			B/=2;
		}
	}
	return result;
}

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

void init()
{
	memset(traversed,0,sizeof(traversed));
	for(int i=1;i<=ModMax;i++)	mod_period[i] = 1;
	for(int i=2;i<=ModMax;i++){
		if( traversed[i] )	continue;
		int previous = 1;
		int prime_number = i;
		while(prime_number <= ModMax){
			for(int j=1;j<=ModMax;j++){
				if( j%i == 0 )	continue;
				int number = j*prime_number;
				if( number > ModMax )	break;
				mod_period[number] = lcm(mod_period[number], (prime_number - previous));
				traversed[number] = 1;
				if( j!=1 )
					PreModulo_Factorization[number].pb(mp(mp(i,j),(prime_number*Inverse(prime_number,j))%(number)));
				else
					PreModulo_Factorization[number].pb(mp(mp(i,j),0));	
			}
			previous = previous*i;
			prime_number = prime_number*i;
		}
	}
}

pair<int,ll> times_mod_val[2][ModMax+2];
int Contraction_Array[ModMax+2];

//Initially current_modulo = previous_modulo
//N,M and start wont change in recursion and start = depth in the begining
void recursive_solve(int N,int M,int start,int L,int modulo,int depth)
{
	//printf("%d is modulo\n",modulo);
	int curr = depth & 1;
	int pre = curr^1;

	//Base Case
	if( modulo == 2 ){
		times_mod_val[curr][1] = mp(depth,powermod(N%M,L,M));
		if( start == depth ){
			printf("%lld\n",times_mod_val[curr][1].second);
		}
		return;
	}
	if( L == 1 ){
		for(int i=1;i<=N;i++){
			int value = InputArray[i]%modulo;
			if( times_mod_val[curr][value].first == depth )	times_mod_val[curr][value].second += 1;
			else	times_mod_val[curr][value] = mp(depth,1);
			if( times_mod_val[curr][value].second >= M )	times_mod_val[curr][value].second-=M;
		}
		return;
	}

	int next_modulo = mod_period[modulo];

	recursive_solve(N,M,start,L-1,next_modulo,depth+1);

	memset(Contraction_Array,0,sizeof(int)*(modulo+1));
	for(int i=1;i<=N;i++){
		int x = InputArray[i]%modulo;
		//InputArray[i]%=modulo;
		for(int j=0;j<PreModulo_Factorization[modulo].size();j++){
			if( InputArray[i]%PreModulo_Factorization[modulo][j].first.first == 0 ){
				x = ((InputArray[i]%PreModulo_Factorization[modulo][j].first.second)*(PreModulo_Factorization[modulo][j].second))%modulo;
				break;
			}
		}
		Contraction_Array[x] ++;
	}

	for(int base = 0;base<modulo;base++){
		if( Contraction_Array[base] == 0 )	continue;
		ll value = 1;
		for(int power=0;power<next_modulo;power++){
			if( times_mod_val[pre][power].first == (depth + 1) ){
				ll total_times = ((ll)(times_mod_val[pre][power].second)*(ll)Contraction_Array[base])%M;
				if( times_mod_val[curr][value].first == depth )	times_mod_val[curr][value].second += total_times;
				else	times_mod_val[curr][value] = mp(depth,total_times);
			}
			value = (value*base)%modulo;
		}
	}
	for(int i=0;i<modulo;i++)	times_mod_val[curr][i].second %= M;

	if( depth == start ){		//starting point...
		int Answer = 0;
		for(int i=1;i<M;i++){
			if( times_mod_val[curr][i].first == depth ){
				Answer = Answer + times_mod_val[curr][i].second*i;
				Answer %= M;
			}
		}
		printf("%d\n",Answer);
	}
}

void solve(int J)
{
	int N,M;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		assert(scanf("%d",&InputArray[i])==1);
	}
	recursive_solve(N,M,J,N,M,J);
}

int main()
{
	init();
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		solve((i)*50);
	}
	return 0;
}