We consider the distance between positive integers in this problem, defined as follows. A single operation consists in either multiplying a given number by a prime number or dividing it by a prime number (if it does divide without a remainder). The distance between the numbers $a$ and $b$, denoted $d(a,b)$, is the minimum number of operations it takes to transform the number $a$ into the number $b$. For example, $d(69,42)=3$.

Observe that the function $d$ is indeed a distance function - for any positive integers $a$, $b$, and $c$ the following hold:

• the distance between a number and itself is 0: $d(a,a)=0$,
• the distance from $a$ to $b$ is the same as from $b$ to $a$: $d(a,b)$, and
• the triangle inequality holds: $d(a,b)+d(b,c) \ge d(a,c)$.

A sequence of $n$ positive integers, $a_1, a_2, \ldots, a_n$, is given. For each number $a_i$ we have to determine $j$ such that $j \ne i$ and $d(a_i, a_j)$ is minimal.

Input

In the first line of standard input there is a single integer $n$ ($2 \le n \le 100,000$). In the following $n$ lines the numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1,000,000$) are given, one per line.

In tests worth 30% of total point it additionally holds that $n \leq 1\,000$.

Output

Your program should print exactly $n$ lines to the standard output, a single integer in each line. The $i$-th line should give the minimum $j$ such that $1 \le j \le n$, $j \ne i$ and $d(a_i, a_j)$ is minimal.

Example

Input

6
1
2
3
4
5
6

Output

2
1
1
2
1
2