BlueTube Park

Time limit2sMemory limit1024 MB

Summary

For each A_i, find the smallest index j (j not equal to i) whose value is closest in prime-operation distance, where each multiply or divide by a prime counts as one step.

Level: Hard8 of 10
Topics: Number theory, Hash map, Brute force
Solved: No attempts yet

Problem

Uncle Pasha likes to walk in the BlueTube park. Sometimes people get abducted by aliens during their walks. Unfortunately, this happened to our hero.

The aliens asked Pasha to solve a hard problem, whose optimal solution would help them conquer the world. The problem is as follows: you are given a list of $N$ natural numbers $A_i$ . The numbers are indexed from 1. For each $i$ , find the minimal $j$ ( $j \ne i$ ) such that $dist(A_i, A_j) \le dist(A_i, A_k)$ for every $k$ ( $1 \le k \le N$ , $k \ne i$ ).

$dist(x, y)$ is the minimal number of operations needed to turn $x$ into $y$ . In one operation, the aliens can multiply or divide a number by any prime. A prime is a number with exactly two distinct divisors, 1 and itself. For example, $dist(10, 24) = 4$ .

Input

The first line contains the number $N$ ( $1 \le N \le 10^5$ ), the number of values in the list.

Each of the next $N$ lines contains one value $A_i$ ( $1 \le A_i \le 10^6$ ), starting from $A_1$ .

Output

Print $N$ lines, one number per line. Line $i$ must contain the required index $j$ for $i$ .

Examples1

Example 1
Input
```
6
1
2
3
4
5
6
```
Expected output
```
2
1
1
2
1
2
```