P3532 [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.