#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t,n,mods,f[N],p[N],res,dy[N],idx,cs,inv[N];
int pows(int a,int b){
	if(b==0)return 1;
	int res=pows(a,b>>1);
	res=res*res%mods;
	if(b&1)res=res*a%mods;
	return res;
}
unordered_map<int,int>q;
vector<int>g[N];
int fdl(int x,int y){
	auto w=lower_bound(g[x].begin(),g[x].end(),y);
	if(w==g[x].begin())return 0;
	return *(--w);
}
int fdr(int x,int y){
	auto w=upper_bound(g[x].begin(),g[x].end(),y);
	if(w==g[x].end())return 0;
	return *w;
}
void solve(int a,int b){
	int k=p[b]*inv[a]%mods,invk=p[a]*inv[b]%mods;
	int nw=p[a],ans=2;
	while(1){
		nw=nw*invk%mods;
		if(!q.count(nw))break;
		a=fdl(q[nw],a);
		if(!a)break;
		ans++;
	}
	nw=p[b];
	while(1){
		nw=nw*k%mods;
		if(!q.count(nw))break;
		b=fdr(q[nw],b);
		if(!b)break;
		ans++;
	}
	res=max(res,ans);
	cs+=ans;
}
signed main(){
	srand(time(0));
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		res=0;
		q.clear();idx=0;
		cin>>n>>mods;
		for(int i=1;i<=n;i++){
			cin>>p[i];
			inv[i]=pows(p[i],mods-2);
			if(!q.count(p[i]))q[p[i]]=++idx;
			g[q[p[i]]].push_back(i);
		}
		cs=0;
		if(n>50){
			while(1){
				int i=1ll*rand()*rand()%(n-1)+1;
			    solve(i,i+1);
			    if(i<n-1)solve(i,i+2);
				if(cs>22*n)break;
			}
		}
		else{
			for(int i=1;i<n;i++){
		 		solve(i,i+1);
		        if(i<n-1)solve(i,i+2);
			}
		}
		if(res<n/2.0)cout<<"-1\n";
		else cout<<res<<"\n";
	}
}