Problem: We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

Output

Print n lines: the i-th line should contain "YES" (without the quotes), if number xi is Т-prime, and "NO" (without the quotes), if it isn't.

Examples

Input

3
4 5 6


Output

YES
NO
NO

Note

The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Random;
import java.util.StringTokenizer;

    public class Test {
            static BufferedReader reader;
            static StringTokenizer tokenizer;
            static PrintWriter writer;

            static int nextInt() throws IOException {
                    return Integer.parseInt(nextToken());
            }

            static long nextLong() throws IOException {
                    return Long.parseLong(nextToken());
            }

            static double nextDouble() throws IOException {
                    return Double.parseDouble(nextToken());
            }

            static String nextToken() throws IOException {
                    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                            tokenizer = new StringTokenizer(reader.readLine());
                    }
                    return tokenizer.nextToken();
            }

            public static void main(String[] args) throws IOException {
                    reader = new BufferedReader(new InputStreamReader(System.in));//new FileReader("generator.txt"));
                    tokenizer = null;
                    writer = new PrintWriter(System.out);
                    solve();
                    reader.close();
                    writer.close();
            }
            
            private static void solve() throws IOException {
            
                int n=0;
                n=nextInt();
                for (int i=0;i<n;i++)
                {
                    long r=nextLong();
                    long t=(long)Math.sqrt(r);
                    if (t*t==r)
                        if (check(t))
                            writer.println("YES");
                        else
                            writer.println("NO");
                    else
                        writer.println("NO");
                }        
            }
            private static boolean check(long x){
                
                if (x==2)
                    return true;
                if (x==1)
                    return false;
                long y=(long)Math.sqrt(x);
//              long z=Math.min(y-1, x);
                long p=x/2;
                if (p*2==x)
                    return false;
                for (long i=3;i<y+1;i+=2)
                {
//                  double t=Math.pow(i, x-1);
//                  if (t%x!=1)
                    long t=x/i;
                    if (t*i==x)
                        return false;
                }
                return true;
            }
           


    }