#include<iostream>
#include<vector>
#include<math.h>
#include<set>
#include<queue>
#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<string.h>
using namespace std;
#define ll long long
#define pb push_back
#define po pop_back
#define mp make_pair
#define FOR(i,a,b) for(long long int i=a;i<=b;i++)
#define NFOR(i,a,b) for(long long int i=a;i>=b;i--)
int main()
{
ll t;
cin>>t;
vector<ll>v;
while(t--)
{
ll n,c,i,j,y;
cin>>n;
ll a[n];
ll dp[n];
FOR(i,0,n-1)
{
cin>>a[i];
dp[i]=1;
}
FOR(i,0,n-2)
{
    y=a[i];
    FOR(j,i+1,n-1)
    {
        if(__gcd(y,a[j])>1)
        {
            dp[j]=max(dp[i],dp[j]+1);
        }
    }
}
FOR(i,0,n-1)
cout<<dp[i]<<" ";
}
return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzZXQ+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxjc3RkaW8+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8aW9tYW5pcD4KI2luY2x1ZGU8c3RyaW5nLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcG8gcG9wX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBGT1IoaSxhLGIpIGZvcihsb25nIGxvbmcgaW50IGk9YTtpPD1iO2krKykKI2RlZmluZSBORk9SKGksYSxiKSBmb3IobG9uZyBsb25nIGludCBpPWE7aT49YjtpLS0pCmludCBtYWluKCkKewpsbCB0OwpjaW4+PnQ7CnZlY3RvcjxsbD52Owp3aGlsZSh0LS0pCnsKbGwgbixjLGksaix5OwpjaW4+Pm47CmxsIGFbbl07CmxsIGRwW25dOwpGT1IoaSwwLG4tMSkKewpjaW4+PmFbaV07CmRwW2ldPTE7Cn0KRk9SKGksMCxuLTIpCnsKICAgIHk9YVtpXTsKICAgIEZPUihqLGkrMSxuLTEpCiAgICB7CiAgICAgICAgaWYoX19nY2QoeSxhW2pdKT4xKQogICAgICAgIHsKICAgICAgICAgICAgZHBbal09bWF4KGRwW2ldLGRwW2pdKzEpOwogICAgICAgIH0KICAgIH0KfQpGT1IoaSwwLG4tMSkKY291dDw8ZHBbaV08PCIgIjsKfQpyZXR1cm4gMDsKfQ==

NAoyIDMgMSA0

4
2 3 1 4