#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005;
const int maxm=6000005;
const int INF=0x3f3f3f3f;
int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}
	return ret*f;
}
int n,N=1000000,cnt,tot;
bool is_prime[maxn],vis[maxn];
int lnk[maxn],son[maxm],nxt[maxm],prime[maxn],a[maxn],que[maxn];
struct node{
	int dep,fr;	
	node(){dep=INF;fr=0;}
	node(int d,int f){dep=d;fr=f;}
	node operator+(const int l)const{return (node){dep+l,fr};}
	bool operator<(const node &B)const{return (dep<B.dep)||(dep==B.dep&&fr<B.fr);} 
}dis[maxn],ans[maxn];
void update(node &A,node B){
	ans[A.fr]=min(ans[A.fr],(node){A.dep+B.dep,B.fr});
	ans[B.fr]=min(ans[B.fr],(node){A.dep+B.dep,A.fr});
	A=min(A,B);
}
void add_e(int x,int y){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;}
void sieve(){
	for(int i=2;i<=N;++i){
		if(!is_prime[i]){
			prime[++tot]=i;
		}
		for(int j=1;j<=tot&&i*prime[j]<=N;++j){
			is_prime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
void BFS(){
	int hed=0,til=0;
	for(int i=1;i<=n;++i){
		if(!vis[a[i]]){
			que[++til]=a[i];
			vis[a[i]]=1;
		}
	}
	while(hed<til){
		int now=que[++hed];
		for(int j=lnk[now];j;j=nxt[j]){
			if(dis[son[j]].fr==dis[now].fr) continue;
			update(dis[son[j]],dis[now]+1);
			if(!vis[son[j]]){
				vis[son[j]]=1;
				que[++til]=son[j];
			}
		}
	}
}
int main(){
	sieve();
	for(int i=1;i<=N;++i){
		for(int j=1;j<=tot&&i*prime[j]<=N;++j){
			add_e(i,i*prime[j]);
			add_e(i*prime[j],i); 
		}
	}
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		update(dis[a[i]],(node){0,i});
	}
	BFS();
	for(int i=1;i<=n;++i) printf("%d\n",ans[i].fr); 
	return 0;
}