29295번 - Парк BlueTube 다국어

Как Вы уже поняли, дядя Паша любит гулять в парке $BlueTube$. Иногда случается, что во время прогулок людей похищают инопланетяне. К сожалению, именно это и случилось с нашим героем.

Инопланетяне попросили Пашу решить сложную задачу, оптимальное решение которой поможет им покорить мир. Задача была следующая: дан список из $N$ натуральных чисел $A_i$. Числа в списке нумеруются натуральными числами, начиная с единицы. Для каждого $i$ нужно найти минимальное $j$ ($j \ne i$) такое, что $dist(A_i, A_j) \le dist(A_i, A_k)$ для любого $k$ ($1 \le k \le N$, $k \ne i$). Инопланетяне считают, что $dist(x, y)$ --- это минимальное количество операций, необходимых для того, чтобы из числа $x$ получить число $y$. За одну операцию инопланетяне умеют умножать или делить число на любое простое число. Простым называется число, у которого ровно два различных делителя --- единица и оно само. Например, $dist(10, 24) = 4$.

Паша испугался, поэтому сразу позвонил Роме. Как Вы уже догадались, Рома --- так себе программист, но помимо этого он еще и увлекся решением примеров по математическому анализу. Рома дал Паше Ваш номер, поэтому только Вы можете спасти нашего героя! Решите поставленную задачу, чтобы Паша мог вернуться обратно в $BlueTube$.

В первой строке входного файла содержится число $N$ ($1 \le N \le 10^5$) --- количество чисел в списке.

В следующих $N$ строках входного файла последовательно заданы числа $A_i (1 \le A_i \le 10^6)$ по одному в строке, начиная с $A_1$.

Выведите $N$ чисел, по одному в строке. В строке номер $i$ должен быть искомый индекс $j$ для этого $i$.