In this task let's consider distance between two positive integers defined as below.

Single operation is: multiplying some number by prime number or dividing some number by prime number (we can divide only when remainder is equal to 0.)

Distance d between two numbers a, b is minimum number operations to convert one number to another.

For example d(69, 42) = 3.

This distance is very similar to well-known term "distance" in real human life:

• d(a, a) = 0, distance number to itself is 0.
• d(a, b) = d(b, a) distance from a→b is equal to b→a.
• d(a, b) + d(b, c) ≥ d(a, c) triangle equation is true too.

With given n number you have to determine for each i-th of those numbers closest number a_j from set that i ≠ j and if there is many numbers with equal, smallest distance, you have to pick number with smallest index

Input

In first line - number n ≤ 10⁵.

In next n lines - i-th number. Every number is not greater than 10⁶.

Output

You have to output n lines.

I-th line should contain index of closest number (if there are many answers, please output smallest index.)

Example

Input:
6
1
2
3
4
5
6

Output:
2
1
1
2
1
2