\begin{problem}{Парк BlueTube}{bluetube.in}{bluetube.out}{2 секунды}{256 мегабайт}

%Автор задачи: Роман Рубаненко
%Автор условия: Роман Рубаненко

Как Вы уже поняли, дядя Паша любит гулять в парке $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$. 

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

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

\Example
\Examples
\begin{example}%
\exmp{
6
1
2
3
4
5
6
}{
2
1
1
2
1
2
}%
\end{example}

\Testing
Первая группа тестов состоит из тестов, для которых выполняется ограничение $N \le 1000$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $30$ баллов.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение $N \le 10^5$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $70$ баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех группах тестов, кроме последней, 
нажав на ссылку <<\texttt{Request feedback}>> на вкладке <<\texttt{Runs}>>.

\end{problem}
