#pragma comment(linker, "/STACK:64000000")
#include <algorithm>
#include <memory.h>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <queue>

using namespace std;
#define prev privet1
#define next privet2
#define y1 privet3
#define rank privet4
#define left privet5
#define right privet6
#define y0 privet7
#define count privet8

const double pi = 3.141592653589793238;

void ensureLimit(long long n, long long l, long long r)
{
	assert(l <= n && n <= r);
}

const int MAX = 1000000;

struct tt
{
	int dist, num;
	tt(int dist, int num) : dist(dist), num(num) {}
	tt() {}
};

tt ot[1000333][2];
int num[1000333][2], kk;
int y, n, i, x, k, j, r, prime[100333], value[1000333], deg[30], list[2222], cnt, w[33], seq[1000333], p[1000333];
bool used[1000333];
int count[1000333], primes[1000333];

inline bool Less(tt a, tt b) 
{
	return (a.dist < b.dist || (a.dist == b.dist && a.num < b.num));
}

inline tt Min(tt a, tt b)
{
	if (Less(a, b)) return a;
	else return b;
}

void relax(tt &ot0, tt &ot1, tt anc1, tt anc2)
{
	if (anc1.num != 0) 
	{
		if (Less(anc1, ot0) && anc1.num != ot0.num) 
		{
			ot1 = ot0;
			ot0 = anc1;
		}
		else if (Less(anc1, ot0)) ot0.dist = anc1.dist;
		else if (Less(anc1, ot1) && anc1.num != ot0.num) ot1 = anc1;
	}
	if (anc2.num != 0) 
	{
		if (Less(anc2, ot0) && anc2.num != ot0.num) 
		{
			ot1 = ot0;
			ot0 = anc2;
		}
		else if (Less(anc2, ot0)) ot0.dist = anc2.dist;
		else if (Less(anc2, ot1) && anc2.num != ot0.num) ot1 = anc2;
	}
}

void dfs(int v)
{
	used[v] = true;
	for (int i = 1; i <= kk && (prime[i] * v <= MAX); i++)
	{
		int u = prime[i] * v;
		if (!used[u]) dfs(u);
		relax(ot[v][0], ot[v][1], tt(ot[u][0].dist + 1, ot[u][0].num), tt(ot[u][1].dist + 1, ot[u][1].num));
	}
}

int distUp(int x, int y)
{
	return count[x / y];
}

void rec(int x, int d)
{
	if (x == cnt + 1)
	{
		r++;
		list[r] = d;
		return;
	}
	for (int i = 0; i <= deg[x]; i++)
	{
		rec(x + 1, d);
		d = d * w[x];
	}
}

int main()
{
	freopen("bluetube.in", "r", stdin);
	freopen("bluetube.out", "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= 1000000; i++)
		ot[i][0] = ot[i][1] = tt(100, 0);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		seq[i] = x;
		if (num[x][0] == 0) 
			{
				num[x][0] = i;
				ot[x][0] = tt(0, i);
			}
		else if (num[x][1] == 0) 
			{
				num[x][1] = i;
				ot[x][1] = tt(0, i);
			}
	}
	p[1] = 1;
	for (i = 2; i <= MAX; i++)
		if (p[i] == 0)
		{
			kk++;
			prime[kk] = i;
			for (int x = i; x <= MAX; x += i)
			{
				p[x] = i;
			}
		}
	for (i = 1; i <= MAX; i++)
	{
		x = i;
		while (x > 1)
		{
			x = x / p[x];
			count[i]++;
		}
	}
	dfs(1);
	for (i = 1; i <= n; i++)
	{
		cnt = 0;
		x = seq[i];
		while (x > 1)
		{
			cnt++;
			w[cnt] = p[x];
			deg[cnt] = 0;
			while (x % w[cnt] == 0)
			{
				deg[cnt]++;
				x = x / w[cnt];
			}
		}
		r = 0;
		rec(1, 1);
		x = seq[i];
		int id, u;
		tt ans;
		if (ot[x][0].num != i) ans = ot[x][0];
		else ans = ot[x][1];
		cnt = r;
		for (j = 1; j <= cnt; j++)
		{
			u = list[j];
			if (ot[u][0].num != i && Less(tt(distUp(x, u) + ot[u][0].dist, ot[u][0].num), ans)) ans = tt(distUp(x, u) + ot[u][0].dist, ot[u][0].num);
			if (ot[u][1].num != i && Less(tt(distUp(x, u) + ot[u][1].dist, ot[u][1].num), ans)) ans = tt(distUp(x, u) + ot[u][1].dist, ot[u][1].num);			
		}
		printf("%d\n", ans.num);
	}
}
