Problem Description

Given $T$ positive integers $a_i$, for each $a_i$ determine whether it can be written in the form $x_1^{y_1} \cdot x_2^{y_2}$, where $x_1, x_2$ are positive integers, and $y_1, y_2$ are integers with $y_1 \ge 2$ and $y_2 \ge 2$.

Input Format

The first line contains an integer $T$, representing the number of queries.

The next $T$ lines each contain a positive integer $a_i$.

Output Format

For each query, if $a_i$ can be written in the form described in the statement, output yes; otherwise output no.

7
2
6
12
4
8
24
72

no
no
no
yes
yes
no
yes

Hint

Sample Explanation

The $4$th, $5$th, and $7$th numbers can be written as:

$$\begin{aligned} &a_{4}=2^{2} \times 1^{2} ; \\ &a_{5}=2^{3} \times 1^{2} ; \\ &a_{7}=2^{3} \times 3^{2} 。 \end{aligned}$$

Constraints and Notes

For $10\%$ of the testdata, $1 \leq T \leq 200, a_i \leq 10^{9}$.

For $30\%$ of the testdata, $1 \leq T \leq 300, a_i \leq 10^{18}$.

For $60\%$ of the testdata, $1 \leq T \leq 10000, a_i \leq 10^{18}$.

For all testdata, $1 \leq T \leq 100000, 1 \leq a_i \leq 10^{18}$.

Lanqiao Cup 2022 Provincial Contest, Group A, Problem I.

Translated by ChatGPT 5