题目描述

对于两个正整数 $a,b$，这样定义函数 $d(a,b)$：

每次操作可以选择一个质数 $p$，将 $a$ 变成 $a\times p$ 或 $\dfrac{a}{p}$，如果选择变成 $\dfrac{a}{p}$ 就要保证 $p$ 是 $a$ 的约数，$d(a,b)$ 表示将 $a$ 变成 $b$ 所需的最少操作次数。

例如 $d(69,42)=3$。

现在给出 $n$ 个正整数 $a_{1\dots n}$，对于每个 $a_i$，求最小的 $j$ 使得 $i\not =j$ 且 $d(a_i,a_j)$ 最小。

输入格式

第一行一个正整数 $n$。
接下来一行 $n$ 个正整数 $a_{1\dots n}$。

输出格式

输出 $n$ 行，依次表示答案。

6
1
2
3
4
5
6

2
1
1
2
1
2

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq a_i\leq 10^6$。