在本题中，我们考虑正整数之间的距离，定义如下：一次操作是指将给定的数乘以一个质数，或者除以一个质数（前提是该数能被该质数整除）。两个数 $a$ 和 $b$ 之间的距离 $d(a,b)$ 定义为将 $a$ 变换为 $b$ 所需的最少操作次数。例如，$d(69,42)=3$。

观察可知，函数 $d$ 确实是一个距离函数——对于任意正整数 $a$、$b$ 和 $c$，以下性质成立：

• 一个数与自身的距离为 0：$d(a,a)=0$；
• 从 $a$ 到 $b$ 的距离与从 $b$ 到 $a$ 的距离相同：$d(a,b)=d(b,a)$；
• 满足三角不等式：$d(a,b)+d(b,c) \ge d(a,c)$。

给定一个包含 $n$ 个正整数的序列 $a_1, a_2, \ldots, a_n$。对于每个数 $a_i$，我们需要确定一个下标 $j$，使得 $j \ne i$ 且 $d(a_i, a_j)$ 最小。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 100,000$)。接下来的 $n$ 行每行给出一个数 $a_i$ ($1 \le a_i \le 1,000,000$)。

在总分占比 30% 的测试点中，额外满足 $n \le 1,000$。

输出格式

程序应向标准输出打印恰好 $n$ 行，每行一个整数。第 $i$ 行应输出满足 $1 \le j \le n$、$j \ne i$ 且 $d(a_i, a_j)$ 最小的下标 $j$。

样例

输入格式 1

6
1
2
3
4
5
6

输出格式 1

2
1
1
2
1
2