DISTX - Distance

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 aj 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 ≤ 105.

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

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

Added by:Krzysztof Lewko
Date:2011-11-15
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:19th POI 1st stage

hide comments
2011-11-23 12:40:32 Krzysztof Lewko
yup, you are right.
2011-11-23 12:40:22 Thomas Dybdahl Ahle
The triangle inequality in the description should be using a >= rather than a >.
2011-11-23 12:40:22 Krzysztof Lewko
Sorry, was translating it in night, now it's corrected.
2011-11-23 12:40:22 [Rampage] Blue.Mary
The range of N & the numbers?

Edit: I've found the original problem. It states n<=10^5, each of the numbers <= 10^6.

Last edit: 2011-11-15 11:01:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.