#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<random>
#include<algorithm>
#define N 134217729
#define M 8
#define S 20
using namespace std;
mt19937 RAND(random_device{}());
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,t,length,delta[M+1],v[N+1];
short F[N+1];
long long pw[S+1],tong[S+1];
long long fast_pow(long long a,long long b,long long p)
{
	long long res=1,mul=a;
	while (b)
	{
		if (b&1) res=(__int128)(res)*mul%p;
		mul=(__int128)(mul)*mul%p,b>>=1;
	}
	return res;
}
long long gcd(long long a,long long b)
{
	if (!b) return a;
	return gcd(b,a%b);
}
bool miller_rabin(long long x)
{
    if (x<=N) return F[x]==1;
	if (!(x&1)) return 0;
	long long c,d=x-1;
	int cnt=0;
	while (!(d&1)) d>>=1,cnt++;
	for (int i=1;i<=10;++i)
	{
		c=RAND()%(x-1)+1;
		if (fast_pow(c,x-1,x)!=1) return 0;
		pw[0]=fast_pow(c,d,x);
		for (int j=1;j<=cnt;++j) pw[j]=(__int128)(pw[j-1])*pw[j-1]%x;
		for (int j=cnt-1;j>=0;--j)
		{
			if (pw[j]==x-1) break;
			if (pw[j]!=1) return 0;
		}
	}
	return 1;
}
long long pollard_rho(long long x)
{
	if (x<=N) return v[x];
	long long c=RAND()%(x-1)+1,s,t=0,d,ds;
	for (int i=1;;i<<=1)
	{
		s=t,d=1;
		for (int j=1;j<=i;++j)
		{
			t=((__int128)(t)*t+c)%x,d=(__int128)(d)*abs(s-t)%x;
			if (j%127==0)
			{
				ds=gcd(d,x);
				if (ds!=1) return ds;
			}
		}
		ds=gcd(d,x);
		if (ds!=1) return ds;
	}
}
void solve(long long x)
{
	if (miller_rabin(x))
	{
		tong[++length]=x;
		return;
	}
	long long d;
	while (1)
	{
		d=pollard_rho(x);
		if (d!=x)
		{
			solve(d),solve(x/d);
			return;
		}
	}
	return;
}
int calc(int x)
{
	if (F[x]==1) return 1;
	if (F[x]==2) return 2;
	for (int i=1;i<=t;++i)
		if (F[x*delta[i]+1]==1)
			return 2;
	if (F[x]==3) return 3;
	for (int i=1;i<=t;++i)
		if (F[x*delta[i]+1]==2)
			return 3;
	length=0,solve(x);
	vector<int>p;
	for (int i=1;i<=length;++i) p.push_back(tong[i]);
	sort(p.begin(),p.end());
	for (int i=0;i<p.size();++i)
		if (i+1==p.size()||p[i]!=p[i+1])
		{
			for (int j=1;j<=t;++j)
				if (F[(x/p[i])*delta[j]+1]==1)
					return 3;
		}
	if (t>2) return 4;
    if (F[x]==4) return 4;
	for (int i=1;i<=t;++i)
		if (F[x*delta[i]+1]==3)
			return 4;
	for (int i=1;i<=t;++i)
		for (int j=1;j<=t;++j)
		{
			length=0,pollard_rho((1ll*x*delta[i]+1)*delta[j]+1);
			if (length==2) return 4;
		}
	for (int i=1;i<=t;++i)
		for (int j=1;j<=t;++j)
			for (int w=1;w<=t;++w)
				if (miller_rabin(1ll*((1ll*x*delta[i]+1)*delta[j]+1)*delta[w]+1))
					return 4;
	for (int i=0;i<p.size();++i)
		if (i+1==p.size()||p[i]!=p[i+1])
		{
			for (int j=1;j<=t;++j)
				for (int w=1;w<=t;++w)
					if (miller_rabin((1ll*x*delta[j]+1)*delta[w]+1))
						return 4;
			for (int j=1;j<=t;++j)
				if (F[(x/p[i])*delta[j]+1]==2)
					return 4;
			for (int j=i;j<p.size();++j)
				if ((j+1==p.size()||p[j]!=p[j+1])&&(x%p[i])/p[j]==0)
					for (int w=1;w<=t;++w)
						if (F[(x/p[i]/p[j])*delta[w]+1]==1)
							return 4;
		}
	return 5;
}
int main()
{
	for (int i=2;i<=N;++i)
		if (!v[i])
		{
			F[i]=1;
			for (int j=(i<<1);j<=N;j+=i) v[j]=i;
		}
	for (int i=2;i<=N;++i)
		if (v[i])
			F[i]=F[i/v[i]]+1;
	T=read();
	while (T--)
	{
		n=read(),t=read(),length=0;
		for (int i=1;i<=t;++i) delta[i]=read();
		printf("%d\n",calc(n));
	}
	return 0;
}