Untitled

#include<iostream>
#include<vector>
#include<map>
#include<sstream>
#include<math.h>
#include<set>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include <list>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

#define debug(x) cout << #x << " = " << x << "\n";
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz size()
#define pb push_back
#define mp make_pair
#define fr(i, n) for(i=0;i<n;i++)
#define fr2(i, a, n) for(i=a;i<n;i++)
#define mem(a, n) memset(a, n, sizeof(a))
typedef vector<int> VI;
typedef long long LL;
typedef vector<string> VS;
typedef stringstream SS;
vector<int> v[15];
int l;
char vis[15];
                char a[1000000];
LL dp[15][15];
int gcd(int a, int b) {
        cout << a << " " << b << endl;
        if(b==0)
                return a;
        return (b, a%b);
}
const int mod = 1000000007;
LL solve(int sx, int sy, int r) {
        if(r==l-1)
                return 1;
//      cout << sx << " " << sy << " " << r << endl;
        LL &d = dp[sx][sy];
        if(d!=-1)
                return d;
        d = 0;
        int i, j;
        for(i=0;i<l;i++) {
                if(vis[i])
                        continue;
                for(j=0;j<v[i].sz;i++) {
                        if(std::__gcd(v[i][j], v[sx][sy])==1)
{
                                vis[i] = 1;
                                d += solve(i, j, r+1);
                                vis[i] = 0;
                        }

                }
        }
        return d;

}

int main() {
        int t;
        cin >> t;
        string s;
        int i = 0;
        while(t--) {
                scanf("%d", &l);
                getline(cin, s);
                int k;
                fr(k, l) {
                gets(a);
                s = a;
                SS ss;
                ss << s;
                set<int> se;
                int n;

                while(ss >> n) {
                        se.insert(n);
                }
                set<int> :: iterator it;
                for(it=se.begin();it!=se.end();it++)
                        v[i].pb(*it);
                i++;

                }
                mem(dp, -1);
                LL ans = 0;
                int j;

                for(i=0;i<l;i++) {
                        mem(vis, 0);
                        for(j=0;j<v[i].sz;j++) {
                                vis[i] = 1;
                                ans = (ans + solve(i, j, 0)) % mod;
                                vis[i] = 0;
                        }
                }
                cout << ans << endl;

        }


}