#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define fo(i, start, end) for (ll i = start; i <= end; i++)
#define pfo(i, end, start) for (ll i = end; i >= start; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sortall(v) sort(all(v))
#define sumv(v) accumulate(all(v), 0LL)

const int MAXN = 300000+5;

vector<int> g[MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    
    fo(i, 1, MAXN) {
        for (int j = i; j <= MAXN; j += i) {
            g[j].pb(i);
        }
    }
    
    ll t;
    cin>>t;
    while(t--){
    	ll n;
    	cin>>n; unordered_map <ll,ll> p;
    	fo(i,1,n){
    		ll g;cin>>g; p[g]++;
    	}
    	vector <ll> dp(n+1,-1);
    	if(p[1]>=1){
    		dp[1] = 1;
    	}
    	fo(i,2,n){ll v = 1e18;
    		for(auto u : g[i]){
    			ll p1 = i/u;
    			// if(i==4){
    				// cout<<p1<<" "<<u<<"\n";
    			// }
    			if(dp[p1]!=-1 && dp[u]!=-1){
    				v = min(v,dp[p1]+dp[u]);
    			}
    		}
    		
    		if(v!=1e18){
    			dp[i] = v;
    		}
    		
    		if(p[i]>=1){
    			dp[i] = 1;
    		}	
    	}
    	
    	fo(i,1,n){
    		cout<<dp[i]<<" ";
    	}
    	
    	cout<<"\n";
    }




    return 0;
}