Cube Root Simplification

When learning about cube roots, one interesting exercise is to simplify expressions of the form $$\sqrt[3]{x}$$ into their simplest radical form, that is, to write them as $$a\sqrt[3]{b}$$ where (a) and (b) are positive integers and (b) is as small as possible (i.e. it is not divisible by any perfect cube greater than 1). In this problem, you are given (n) expressions of the form $$\sqrt[3]{x}$$. For each (x), you need to find two integers (a) and (b) satisfying

[ a^3 \times b = x ]

and output the maximum possible (a). For example, for the expression $$\sqrt[3]{125}$$, we have (125 = 5^3 \times 1) so the answer is (5); for $$\sqrt[3]{81}$$, since (81 = 3^3 \times 3), the answer is (3); and for $$\sqrt[3]{52}$$, since no cube greater than (1^3) divides (52), the answer is (1).

inputFormat

The first line contains a positive integer (n), the number of cube root expressions. Each of the following (n) lines contains a positive integer (x). (x) satisfies (1 \le x \le 10^{12}) (or a suitable range based on problem constraints).

outputFormat

Output (n) lines. In each line, print the maximum integer (a) such that (a^3) divides the respective (x).

sample

3
125
81
52

5
3
1