e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Degree numbers

Degree numbers

The number n is called a degree number if its possible to get it from some other number multiplying itself with at least one time. For example 4 is a degree number because 4 = 2 · 2, 27 is also the degree number because 27 = 3 · 3 · 3, 28 is not a degree number. You are given numbers. Are they degree numbers?

Input

The first line contains the number n (1n10).The second line contains n integers, each greater than 1 and less than 109.

Output

Print n lines. Print in the i-th line YES, if the i-th number is a degree number and NO otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
27 28
Output example #1
YES
NO