Kimo loves all sorts of properties of odd numbers. He learned a new algorithm to get all divisors of a certain number.

Help him to determine if a number has odd number of divisors.

Input

t - the number of test cases, then t test cases follows. [t <= 1000]

Each line contains one integer: N [1 <= N <= 10⁹]

Output

For each test case output one line contains "YES" if the given number has odd number of divisors an "NO" otherwise.

Example

Input:
2
4
7

Output:
YES
NO

Explanation

In the first case: divisors of 4 are : (1, 2, 4) and the number of divisors is 3 (odd)

In the second case: divisors of 7 are : (1, 7) and the number of divisors is 2 (even)