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

SAMPLE INPUT
5
1
2
3
4
5

SAMPLE OUTPUT
Yes
Yes
Yes
No
Yes

Explanation

In the given sample case, all numbers from 1 to 5, except 4, are interesting. The number '4' has two proper divisors and both of them are interesting. Hence, it has even number of interesting proper divisors.

见题面

见题面