eolymp
bolt
Try our new interface for solving problems
Problems

Minimum degree of prime

Minimum degree of prime

Time limit 6 seconds
Memory limit 128 MiB

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 data

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

Output data

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

Input example #1
5
2
12
108
36
65536
Output example #1
1
1
2
2
16
Author Anton Lunev
Source Winter School, Kharkov, 2011, Day 6