/*
"An anomaly, I'm Muhammad Ali
  Cause I know one day I'm gonna be the"
                - Greatest, Eminem
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
#define ff first
#define Shazam ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL);
#define ss second
#define all(c) c.begin(),c.end()
#define endl "\n"
#define test() int t; cin>>t; while(t--)
#define fl(i,a,b) for(int i = a ; i <b ;i++)
#define get(a) fl(i,0,a.size())  cin>>a[i];
#define pra(a) fl(i,0,a.size()) cout<<a[i]<<" ";	cout<<endl;
#define pr(a,n) fl(i,0,n) cout<<a[i]<<" ";	cout<<endl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll INF = 2e18;
const int inf = 2e9;
const int mod1 = 1e9 + 7;



int main(){
    Shazam;
    int n; cin >> n;
    vector<ll> a(n);
    get(a);
    unordered_map<ll, ll> dp;
    int lo = *min_element(all(a));
    for(ll x : a){
        for(ll i = 1; i * i <= x && i < lo; i++){
            if(x % i == 0){
                dp[i] = __gcd(dp[i], x);
                if(x / i != i && x / i < lo){
                    dp[x / i] = __gcd(dp[x / i], x);
                }
            }
        }
    }
    int ans = 1;
    for(auto pp : dp){
        ans += (pp.ff == pp.ss);
    }
    cout << ans << endl;
    return 0;
}
// Problem: A - Long Common Subsequence
// Contest: AtCoder - AtCoder Grand Contest 052
// URL: https://atcoder.jp/contests/agc052/tasks/agc052_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1000000007;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define resz resize


#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)


void solve()
{
    int n;
    cin>>n;
    string a,b,c;
    cin>>a>>b>>c;
    for(int i=0;i<n;i++)
    {
    	cout<<"0";
    }
    for(int i=0;i<n;i++)
    {
    	cout<<"1";
    }
    cout<<"0"<<endl;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin>>t;
    while(t--)
        solve();
}