P4446 [AHOI2018 Middle School] Radical Simplification

While learning about cube roots, Keke encountered the following problem: Simplify the following radicals to their simplest forms: (1) $\sqrt[3]{125}$ (2) $\sqrt[3]{81}$ (3) $\sqrt[3]{52}$ This was too easy for Keke, and he quickly got the answers: (1) $5$ (2) $3\sqrt[3]{3}$ (3) $\sqrt[3]{52}$ Keke knows that any radical of the form $\sqrt[3]{x}$ can be simplified to the simplest form $a\sqrt[3]{b}$. He found this interesting and created many similar problems, but soon got overwhelmed, so he asked you for help: Given $n$ radicals of the form $\sqrt[3]{x}$, simplify each to the simplest form $a\sqrt[3]{b}$. For convenience, you only need to output $a$. If you have not learned this topic, you can think of it as: given $n$ positive integers $x$, for each $x$, find integers $a, b$ such that $a^3 \times b = x$, and output the largest integer $a$.

The input has two lines: - The first line contains an integer $n$, the number of radicals of the form $\sqrt[3]{x}$. - The second line contains $n$ positive integers, giving each $x$ in order.

Output $n$ lines, each with a positive integer. The $i$-th line contains the answer for the $i$-th $x$ in the input.

For $100\%$ of the testdata: $1 \le n \le 10000$, $1 \le x \le 10^{18}$. There are 10 test points, numbered $1 \sim 10$, with the following additional guarantees: 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}$ and $x$ is a perfect cube. 7 ~ 8: $n \le 500$, $x \le 10^{18}$. 9 ~ 10: $n \le 10000$, $x \le 10^{18}$. Translated by ChatGPT 5