#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Funkce pro výpočet počtu prvočíselných dělitelů
// Např. 12 = 2*2*3 -> vrátí 3
ll count_prime_factors(ll n) {
ll cnt = 0;
for (ll i = 2; i * i <= n; ++i) {
while (n % i == 0) {
cnt++;
n /= i;
}
}
if (n > 1) cnt++;
return cnt;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
vector<ll> x(n);
vector<ll> cnt(n); // Zde uložíme "výšku" každého leknínu
for (ll i = 0; i < n; i++) {
cin >> x[i];
cnt[i] = count_prime_factors(x[i]);
}
// Procházíme všechny dvojice i < j
for (ll i = 0; i < n; i++){
for (ll j = i + 1; j < n; j++){
// 1. Zkontrolujeme, jestli tam žába vůbec může skočit (dělitelnost)
if (x[j] % x[i] != 0) {
// Pokud nedělí, nemůže skočit, takže barva nehraje roli.
// Vypíšeme třeba barvu 1.
cout << 1 << " ";
}
else {
// 2. Pokud dělí, musíme chytře obarvit
// Použijeme XOR jejich "výšek" (počtu dělitelů)
ll diff = cnt[i] ^ cnt[j];
// Najdeme nejvýznamnější bit (Most Significant Bit)
// __builtin_clzll vrací počet nul zleva u long long (64 bit)
// 63 - clzll nám dá index nejvyšší jedničky (0-indexed)
ll msb_index = 63 - __builtin_clzll(diff);
// Barva je index bitu modulo 3 (+1 aby to bylo 1,2,3)
cout << (msb_index % 3) + 1 << " ";
}
}
// Nový řádek po vypsání všech dvojic pro dané i (volitelné formátování)
// Zadání to asi nevyžaduje, ale pro přehlednost:
// cout << "\n";
}
cout << "\n";
return 0;
}
