Minimum degree of prime

Positive integer n (n > 1) is given. Consider all different prime divisors of n. Each of them is included in the decomposition of n into prime factors in some degree. Find the minimum among these degrees.

Input

First line contains the number of positive integers t (t ≤ 100000). The next t lines contain these numbers. It is guaranteed that each of them does not exceed 10^18.

Output

For each input positive integer n print in a separate line the minimum degree of the occurrence of a prime number in the decomposition of n into prime factors.

Examples