You are given a positive integer n(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.
Assume n = p₁^e1 p₂^e2... p_m^em , where p_i are different prime divisors of n and ei ≥ 1. Your task is to find
the greatest common divisor of e1,e2,..., em.

The first line of the input contains an integer T(1 ≤ T ≤ 10000), denoting the number of test cases.
In each test case, there is only one integer n(2 ≤ n ≤ 10¹⁸).

For each test case, print a single line containing an integer, denoting the answer.