Representation as a Product of Two Perfect Powers

You are given T positive integers \(a_i\). For each \(a_i\), determine whether it can be expressed in the form

\(a_i = x_1^{y_1} \cdot x_2^{y_2}\)

where \(x_1\) and \(x_2\) are positive integers and \(y_1, y_2 \ge 2\) are also positive integers. Note that the numbers \(x_1\) and \(x_2\) can be equal to 1. For example, since \(16 = 4^2 \cdot 1^2\), 16 is a valid number, but 17 cannot be written in such a form.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a single positive integer \(a_i\).

Example:

4
16
17
1
100

outputFormat

For each test case, output a single line with either Yes if \(a_i\) can be represented as \(x_1^{y_1} \cdot x_2^{y_2}\) with \(y_1, y_2 \ge 2\), or No otherwise.

Example:

Yes
No
Yes
Yes

sample

4
16
17
1
100

Yes
No
Yes
Yes