#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

using namespace std;

long long count_ones(long long n, int j) {
    long long cycle = 1LL << (j + 1);
    long long half = 1LL << j;
    long long res = (n / cycle) * half;
    long long rem = n % cycle;
    if (rem >= half) {
        res += rem - half + 1;
    }
    return res;
}

void solve() {
    int n;
    if (!(cin >> n)) return;
    int k = 0;
    while ((1LL << k) <= n) k++;
    
    vector<string> S(k);
    for (int i = 0; i < k; ++i) {
        cin >> S[i];
    }
    
    vector<int> R_req(k);
    for (int j = 0; j < k; ++j) {
        R_req[j] = count_ones(n, j);
    }
    
    vector<int> C_cnt(k);
    for (int i = 0; i < k; ++i) {
        int c = 0;
        for (int j = 0; j < n; ++j) {
            if (S[i][j] == '1') c++;
        }
        C_cnt[i] = c;
    }
    
    vector<int> R_idx(k), S_idx(k);
    iota(R_idx.begin(), R_idx.end(), 0);
    iota(S_idx.begin(), S_idx.end(), 0);
    
    sort(R_idx.begin(), R_idx.end(), [&](int a, int b) {
        return R_req[a] < R_req[b];
    });
    sort(S_idx.begin(), S_idx.end(), [&](int a, int b) {
        return C_cnt[a] < C_cnt[b];
    });
    
    bool ok = true;
    for (int i = 0; i < k; ++i) {
        if (R_req[R_idx[i]] != C_cnt[S_idx[i]]) {
            ok = false;
            break;
        }
    }
    
    if (!ok) {
        cout << 0 << "\n";
        return;
    }
    
    vector<int> val(n, 0);
    for (int i = 0; i < k; ++i) {
        int str_idx = S_idx[i];
        int bit_idx = R_idx[i];
        for (int c = 0; c < n; ++c) {
            if (S[str_idx][c] == '1') {
                val[c] |= (1 << bit_idx);
            }
        }
    }
    
    vector<bool> seen(n + 1, false);
    bool valid = true;
    for (int c = 0; c < n; ++c) {
        if (val[c] < 1 || val[c] > n || seen[val[c]]) {
            valid = false;
            break;
        }
        seen[val[c]] = true;
    }
    
    if (!valid) {
        cout << 0 << "\n";
        return;
    }
    
    long long fact[20];
    fact[0] = 1;
    for (int i = 1; i <= 18; ++i) fact[i] = fact[i - 1] * i;
    
    long long ans = 1;
    int i = 0;
    while (i < k) {
        int j = i;
        while (j < k && C_cnt[S_idx[j]] == C_cnt[S_idx[i]]) {
            j++;
        }
        int m = j - i;
        ans *= fact[m];
        
        vector<int> group_idx;
        for (int l = i; l < j; ++l) {
            group_idx.push_back(S_idx[l]);
        }
        
        sort(group_idx.begin(), group_idx.end(), [&](int a, int b) {
            return S[a] < S[b];
        });
        
        int dup = 1;
        for (size_t l = 1; l < group_idx.size(); ++l) {
            if (S[group_idx[l]] == S[group_idx[l - 1]]) {
                dup++;
            } else {
                ans /= fact[dup];
                dup = 1;
            }
        }
        ans /= fact[dup];
        
        i = j;
    }
    
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}