Benny noticed a random property of numbers. The numbers which followed this property were called as interesting numbers by Benny. Let's dive into what Benny discovered about these numbers.

1 is an interesting number.

For every N > 1 , N is interesting if it has odd number of interesting proper divisors. For example, 2 and 3 are interesting numbers, but 4 is not interesting.

You are given T integers. For each given integer, you have to determine whether it is interesting or not.

Input

The first line of the input contains an integer T denoting the given integers.
The next T lines contain a single integer X

Output

For each number in a single line, print "Yes" if the number is interesting and "No" otherwise (without quotes).

Constraints

1 ≤ T ≤ \(5000\)
1 ≤ X ≤ \(10^{11}\)

Note
\(25\)% of the test files have X ≤ \(10^{6}\).