Distance
Memory limit: 128 MB
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.
Input
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
.
Output
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.
Example
For the input data:
6
1
2
3
4
5
6
the correct result is:
2
1
1
2
1
2
Task author: Wojciech Smietanka.
1.
Recall that a positive integer is prime if and only of it has exactly two distinct divisors: one and itself.