QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100
[0]

# 2098. Distance

Statistics

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)d(a,c).

A sequence of n positive integers, a1,a2,,an, is given. For each number ai we have to determine j such that ji and d(ai,aj) is minimal.

Input

In the first line of standard input there is a single integer n (2n100,000). In the following n lines the numbers a1,a2,,an (1ai1,000,000) are given, one per line.

In tests worth 30% of total point it additionally holds that n1000.

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 1jn, ji and d(ai,aj) is minimal.

Example

Input

6
1
2
3
4
5
6

Output

2
1
1
2
1
2