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.*;
import java.util.*;
 
public class Main {
 
    static long prime ; 
    static boolean p [] = new boolean [1000];
    static List <Integer> l = new ArrayList();
 
 
    public static void main(String[] args) throws UnsupportedEncodingException, IOException {
        Reader.init(System.in);
        StringBuilder r = new StringBuilder();
        sieve();
        int n = Reader.nextInt();
        for (int i = 0; i < n; i++) {
            prime = Reader.nextLong();
            long s = (long)Math.sqrt(prime);
 
            if (s*s!=prime || prime ==1) {
                r.append("NO" + "\n");
            } 
            else {
                if (isPrime(s)) {
                    r.append("YES" + "\n");
                } else {
                    r.append("NO" + "\n");
                }
 
            }
 
        }
        System.out.println(r);
 
    }
 
    public static void sieve() {
        for (int i = 0; i < 1000; i++) {
            p[i]=true;
        }
        p[0]=p[1]=false;
        for (int i = 2; i < 1000; i++) {
            if(p[i]){
            l.add(i);
                for (int j = i+i; j < 1000; j+=i) {
                    p[j]=false;
                }
 
            }
        }
 
 
    }
 
 
 
 
    public static boolean isPrime ( long n ){
 
        for (int i : l) {
         if(i>=n)break; 
         if(n%i==0)
             return false ; 
        }
        return true ;
 
 
        }
 
 
 
 
 
 
 
}
 
class Reader {
 
    static StringTokenizer tokenizer;
    static BufferedReader reader;
 
    public static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(new InputStreamReader(input, "UTF-8"));
        tokenizer = new StringTokenizer("");
    }
 
    public static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    public static String nextLine() throws IOException {
        return reader.readLine();
    }
 
    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
 
    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
 
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}