You are given a positive integer n > 1. Consider all the different prime divisors of n. Each of them is included in the expansion n into prime factors in some degree. Required to find among the indicators of these powers is minimal.
Input
The first line of the input file is given a positive integer T ≤ 50000, number of positive integers n in the file. In the next T line sets these numbers themselves. It is guaranteed that each of them does not exceed 10^18.
Output
For each positive integer n from an input file output in a separate line a minimum degree of occurrence of a prime in the decomposition of n into simple factors.