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\n",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 }

View Code