소인수 거리

양의 정수 사이의 거리를 다음과 같이 정의한다. 한 번의 연산은 어떤 수에 소수를 곱하거나, 그 수를 나누어떨어지게 하는 소수로 나누는 것이다. 두 양의 정수 $a$와 $b$의 거리 $d(a, b)$는 $a$를 $b$로 바꾸는 데 필요한 최소 연산 횟수이다. 예를 들어 $d(69, 42) = 3$이다.

함수 $d$는 실제로 거리의 성질을 만족한다. 모든 양의 정수 $a$, $b$, $c$에 대하여 다음이 성립한다.

• 자기 자신과의 거리는 $0$이다: $d(a, a) = 0$.
• 거리는 대칭이다: $d(a, b) = d(b, a)$.
• 삼각 부등식이 성립한다: $d(a, b) + d(b, c) \ge d(a, c)$.

$n$개의 양의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어진다. 각 $a_i$에 대하여 $j \ne i$이면서 $d(a_i, a_j)$를 가장 작게 하는 인덱스 $j$를 구해야 한다.

첫째 줄에 정수 $n$ ($2 \le n \le 100000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 정수 $a_i$ ($1 \le a_i \le 1000000$)가 한 줄에 하나씩 주어진다.

정확히 $n$개의 줄을 출력하며, 각 줄에 정수 하나를 출력한다. $i$번째 줄에는 $1 \le j \le n$, $j \ne i$이고 $d(a_i, a_j)$가 최소가 되는 인덱스 $j$ 중 가장 작은 값을 출력한다. 즉 $a_i$까지의 거리가 최소가 되는 $j \ne i$ 인덱스들 가운데 가장 작은 인덱스를 출력한다.