Degree numbers#2328

Degree numbers

1 second

128 megabytes

Easy

A number $n$ is called a power number if it can be represented as the power of some positive integer raised to at least the second power.

For example, $4$ is a power number because $4 = 2^{2}$ 4 = 2^2.
The number $27$ is also a power number because $27 = 3^{3}$ 27 = 3^3.
However, $28$ is not a power number.

Determine which of the given numbers are power numbers.

Input

The first line contains the number of integers $n (1 \leq n \leq 10)$ n~(1 \le n \le 10). The second line contains $n$ integers, each greater than $1$ and less than $1 0^{9}$ 10^9.

Output

Print $n$ lines. On the $i$ -th line, print "YES" if the $i$ -th number is a power number, and "NO" otherwise.

Examples

Example 1

Loading

4 = 2^{2}

27 = 3^{3}

n (1 \leq n \leq 10)

1 0^{9}