#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAX 2000020
#define inf 0x3f3f3f3f
using namespace std;
int isprime[MAX],map[610][610],low[610],v[610],vis[610];
int min(int a,int b){
    return a<b?a:b;
} 
void count(){
    int i,j;isprime[1]=1;
    for(i=2;i*i<MAX;++i){
        if(isprime[i])continue;
        for(j=i*i;j<MAX;j+=i)
            isprime[j]=1;
    }
}
int prime(int n){
    int temp,result=0,i,j,pos=1;
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;++i)
        low[i]=map[pos][i];
    vis[pos]=1;
    for(j=1;j<n;++j){
        temp=inf;
        for(i=1;i<=n;++i){
            if(!vis[i]&&temp>low[i]){
                temp=low[i];pos=i;
            }
        }
        if(temp==inf)return -1;
        result+=temp;
        vis[pos]=1;
        for(i=1;i<=n;++i){
            if(!vis[i]&&low[i]>map[pos][i])
                low[i]=map[pos][i];
        }
    }
    return result;
}
int main()
{
    count();
    int t,i,n,m,j;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=1;i<=n;++i){
            scanf("%d",&v[i]);
        }
        memset(map,0x3f,sizeof(map));
        for(i=1;i<=n;++i){
            for(j=1;j<=n;++j){
                if(isprime[v[i]]==0||isprime[v[j]]==0||isprime[v[i]+v[j]]==0){
                    map[i][j]=min(min(v[i],v[j]),abs(v[i]-v[j]));
                }
            }
        }
        printf("%d\n",prime(n));    
    }
    return 0;
}