prime cycle

#include <iostream>
using namespace std;
int n;
int arr[100];
bool check[100];
int tmp[100];
int kq;
bool soNguyenTo(int soA)
{
    if (soA < 2)    
        return false;

    for (int i = 2; i*i <= soA; i++)
    {
        if (soA%i==0)
        {
            return false;
        }
    }
    return true;
}
void backtrack(int k){
	if(k == n - 1){
		if(soNguyenTo(tmp[0]+tmp[n-1])) kq++;
		return;
	}
	for(int i = 1; i < n; i++){
		if(!check[i] && soNguyenTo(tmp[k]+arr[i])){
			check[i] = true;
			tmp[k+1] = arr[i]; 
			backtrack(k+1);
			check[i] = false;
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		for(int i = 0; i < n; i++){
		 cin >> arr[i];
		 check[i] = false;
		}
		check[0] = true;
		tmp[0] = arr[0];
		kq = 0;
		backtrack(0);
		cout << kq << endl;
	}
	return 0;
}