P4446 [AHOI2018初中组] 根式化简

小可可在学习“立方根”的知识时碰到这样的问题： 将下面根式化简为最简根式： (1) $\sqrt[3]{125}$ (2) $\sqrt[3]{81}$ (3) $\sqrt[3]{52}$ 这个问题对于小可可来说太简单了，他很快就算出了答案： (1) $5$ (2) $3\sqrt[3]{3}$ (3) $\sqrt[3]{52}$ 小可可知道任意形如 $\sqrt[3]{x}$ 的根式，化简后一定可以被写成形如 $a\sqrt[3]{b}$ 的最简根式。他觉得这很有趣，就仿照出了不少题，但没一会儿就被密密麻麻的根式绕晕了，于是他向你求助： 给定 $n$ 个形如 $\sqrt[3]{x}$ 的根式，请你将它们化简为形如 $a\sqrt[3]{b}$ 的最简形式，为了方便，你只需要输出其中的 $a$ 即可。 如果你没有学过这部分数学知识，你可以认为题意是：给你 $n$ 个正整数 $x$，对于每一个 $x$，你需要求出整数 $a,b$ 使得 $a^3 \times b = x$，输出最大的整数 $a$ 即可。

输入有两行： 第一行一个整数 $n$，表示有 $n$ 个形如 $\sqrt[3]{x}$ 的根式； 第二行 $n$ 个正整数，依次给出每个$x$。

输出 $n$ 行，每行一个正整数，第 $i$ 行正整数表示你对输入中第 $i$ 个 $x$ 给出的答案。

对于 $100\%$ 的数据满足：$1 \le n \le 10000$，$1 \le x \le 10^{18}$。 本题共 10 个测试点，编号为1 \~ 10，每个测试点额外保证如下： 1 \~ 2： $n \le 10, x \le 10^6$ 3 \~ 4： $n \le 10, x \le 10^9$ 5 \~ 6： $n \le 100, x \le 10^{18}$ 且 $x$ 为完全立方数 7 \~ 8： $n \le 500, x \le 10^{18}$ 9 \~ 10： $n \le 10000, x \le 10^{18}$