#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=1.5e8+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,A[10],lim;const int k=1.5e8;
int pr[M/10],ph,La[M];bitset<M> flag;
ll f[1000],g[1000];int fh,gh;

namespace PR{
	using LL=__int128;
	ll rng(ll n){return (1ll*rnd()<<30^rnd())%n+1;}
	ll mpow(ll x,ll y,ll p){ll ans=1;while(y) y&1&&(ans=(LL)ans*x%p),y>>=1,x=(LL)x*x%p;return ans;}
	int ckp(ll n){
		if(n%2==0||n<3) return n==2;
		int i,t=0;ll y=n-1;while(y%2==0) y>>=1,t++;
		int lim=5;while(lim--){
			ll z=mpow(rng(n-2)+1,y,n);if(z==1) continue;
			for(i=0;i<t;i++) {
				if(z==n-1) break;
				z=(LL)z*z%n;
			}
			if(i==t) return 0;
		}
		return 1;
	}
	ll divide(ll n){
		ll c=rng(n-1);//cerr<<n<<' '<<c<<'\n';
		auto f=[&](ll x){return ((LL)x*x+c)%n;};
		ll l=0,r=f(l);
		int stp=0;ll val=1;
		while(l^r){
			ll vs=(LL)val*abs(l-r)%n;stp++;
			if(vs==0||stp==64){
				ll d=__gcd(val,n);
				if(d>1) return d;
				stp=0;val=abs(l-r);
			}else val=vs;
			l=f(l);r=f(f(r));
		}
		ll d=__gcd(val,n);
		if(d>1) return d;
		return divide(n);
	}
}
ll st[N];int sh;
void calc(ll n){
	if(n==1) return;
	if(n<=k){
		st[++sh]=La[n];calc(n/La[n]);
		return;  
	}
	if(PR::ckp(n)){st[++sh]=n;return;}
	ll p=PR::divide(n);
	calc(p);calc(n/p);
}
void calcs(ll n){
	sh=0;
	if(n<=k){
		while(n^1) st[++sh]=La[n],n/=La[n];
		return;
	}
	for(int i=1;i<=50;i++) while(n%pr[i]==0) st[++sh]=pr[i],n/=pr[i];
	calc(n);
}
void Solve(){
	int i,j;scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) scanf("%d",&A[i]);
	calcs(n);lim=sh;f[fh=1]=n;
	for(int T=1;T+1<lim;T++){
		sort(f+1,f+fh+1);
		fh=unique(f+1,f+fh+1)-f-1;
		gh=fh;copy(f+1,f+fh+1,g+1);fh=0;
		for(int i=1;i<=gh&&T+1<lim;i++){
			for(int j=1;j<=m;j++)if(g[i]*A[j]+1<1e18){
				calcs(g[i]*A[j]+1);
				lim=min(lim,T+sh);
				if(T+2<lim) f[++fh]=g[i]*A[j]+1;
			}
		}
		for(int i=1;i<=gh&&T+2<lim;i++){
			calcs(g[i]);
			for(int j=1;j<=sh;j++) f[++fh]=g[i]/st[j];
		}
		/*if(f.size()>30){
			gdb(f.size());
			cerr<<n<<' '<<m<<' ';
			for(int k=1;k<=m;k++) cerr<<A[k]<<' ';cerr<<'\n';
		} */
	}
	printf("%d\n",lim);
	// if(clock()*1.0/CLOCKS_PER_SEC>11.7) exit(0);
}
void init(){
	for(int i=2;i<=k;i++){
		if(!flag[i]) pr[++ph]=i,La[i]=i;
		for(int j=1;j<=ph&&i*pr[j]<=k;j++) {
			flag[i*pr[j]]=1;La[i*pr[j]]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
}
int main(){
	int t=1;init();
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}