#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;
}
bool check(long long x,int d,int step)
{
	if (d==step-1) return miller_rabin(x);
	for (int i=1;i<=t;++i)
		if (check(x*delta[i]+1,d+1,step))
			return 1;
	length=0,solve(x);
	if (d+length==step) return 1;
	vector<long long>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])&&check(x/p[i],d+1,step))
			return 1;
	return 0;
}
int calc(int x)
{
	for (int step=1;step<=5;++step)
		if (check(x,0,step))
			return step;
	return 6;
}
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();
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),t=read(),length=0;
		for (int i=1;i<=t;++i) delta[i]=read();
		printf("%d\n",calc(n));
	}
	return 0;
}