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 ₁ ^e1p ₂ ^e2... p _m ^em, where p _iare 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.