1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstring> 5 #include <cstdlib> 6 #include <queue> 7 #include <iostream> 8 #include <bitset> 9 using namespace std; 10 #define N 300005 11 #define M 300000 12 #define ll long long 13 int n,a[N],q[N],ans,now,pri[N],cnt,vis[N],used[11],b[N]; 14 void init() 15 { 16 for(int i=2;i<=M;i++) 17 { 18 if(!vis[i])pri[++cnt]=i; 19 for(int j=1;j<=cnt&&i*pri[j]<=M;j++) 20 { 21 vis[i*pri[j]]=1; 22 if(i%pri[j]==0)break; 23 } 24 } 25 } 26 bool cmp(const int &a,const int &b){return q[a]<q[b];} 27 bool check(int x) 28 { 29 int gcd=used[1]; 30 for(int i=2;i<=x;i++)gcd=__gcd(gcd,used[i]);//最大公约数 31 return gcd==1; 32 } 33 void solve() 34 { 35 scanf("%d",&n);memset(vis,0,sizeof(vis)); 36 for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1); 37 cnt=0; 38 // int gcd=a[1];for(int i=2;i<=n;i++)gcd=__gcd(gcd,a[i]);if(gcd!=1){puts("-1");return ;} 39 for(int i=1;i<=n;i++) 40 if(!vis[a[i]]) 41 { 42 b[++cnt]=a[i];//最小的不重复的数 43 for(int j=a[i];j<=M;j+=a[i])vis[j]=1;//排过序，a[i]为最小的倍数，筛选M以内a[i]的倍数 44 } 45 for(int i=1;i<=cnt;i++) 46 for(int j=pri[i];j<=M;j+=pri[i])q[j]++; 47 sort(b+1,b+cnt+1,cmp);//以 这个数以及他的倍数 的出现次数的和 进行排序 48 for(int i=1;i<=cnt;i++){used[1]=b[i];if(check(1)){puts("1");return;}} 49 for(int i=2;i<=7;i++) 50 { 51 for(int cas=1;cas<=100000;cas++) 52 { 53 for(int j=1;j<=i;j++)used[j]=b[rand()%cnt+1]; 54 if(check(i)){printf("%d ",i);return;} 55 } 56 } 57 puts("-1"); 58 } 59 int main() 60 { 61 // freopen("data_structs.in","r",stdin); 62 // freopen("data_structs.out","w",stdout); 63 int T;scanf("%d",&T);init(); 64 while(T--)solve(); 65 }