Description

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$.

Input Format

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 Format

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

3
125 81 52

5
3
1

Hint

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