//NiceDuck
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;
#define FILE "000"
#define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
#define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define MOD 1000000007
#define el "\n"

const int MAX=3e5+5;
int t,n,a[MAX],f[MAX];
vector<pii> g[MAX];
void pre()
{
    foru(i,1,3e5)
    {
        for(int j=1; 1LL*j*j<=i; ++j)
        {
            if(i%j==0) g[i].pb(make_pair(j,i/j));
        }
    }
}
void calc()
{
    foru(i,1,n) f[i]=1e9;
    foru(i,1,n) f[a[i]]=1;
    foru(i,1,n)
    {
        if(f[i]==1) 
        {
            cout<<"1 ";
            continue;
        }
        for(pii p:g[i])
        {
            f[i]=min(f[i],f[p.fi]+f[p.se]);
        }
        cout<<(f[i]==1e9 ? -1 : f[i])<<' ';
    }
    cout<<el;
}

int main()
{
    fastio
    #ifndef ONLINE_JUDGE
    freopen(FILE ".inp","r",stdin);
    freopen(FILE ".out","w",stdout);
    #endif // ONLINE_JUDGE
    
    pre();
    cin>>t;
    while(t--)
    {
        cin>>n; foru(i,1,n) cin>>a[i];
        calc();
    }
    
    return 0;
}