题目描述

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 number1 or dividing it by a prime number (if it does divide without a remainder).

The distance between the numbers and , denoted , is the minimum number of operations it takes to transform the number into the number .

For example, .

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

the distance between a number and itself is 0: , the distance from to is the same as from to : , and the triangle inequality holds: .

A sequence of positive integers, , is given.

For each number we have to determine such that and is minimal.

给你一个序列a[]，定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数)，让a[i]=a[j]的最少操作步数

对于每个i，求d(i,j)最小的j，若有多个解，输出最小的j

输入格式

In the first line of standard input there is a single integer ().

In the following lines the numbers () are given, one per line.

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

输出格式

Your program should print exactly lines to the standard output, a single integer in each line.

The -th line should give the minimum such that: , and is minimal.

6
1
2
3
4
5
6

2
1
1
2
1
2

提示

给你一个序列a[]，定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数)，让a[i]=a[j]的最少操作步数

对于每个i，求d(i,j)最小的j，若有多个解，输出最小的j