#P3532. [POI 2012] ODL-Distance
[POI 2012] ODL-Distance
题目描述
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.
输入格式
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