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.util.*;
import java.io.*;


public class TPrimesB{
    
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        int limit = (int)Math.sqrt(n);
        for (int p = 2; p <= limit; p++) {
            if (prime[p]) {
                for (int i = p * 2; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }
        prime[1] = false;
        return prime;
    }
    public static boolean[] primes; 

    public static String algorithm(long k){ 
        double checkOne = Math.sqrt(k);
        if ((int)checkOne == checkOne){
            int l = (int)checkOne;
            if (primes[l]){
                return "YES";
            }else{
                return "NO";
            }
        }else{
            return "NO";
        }
    }


    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        int n = sc.nextInt();
        Random rd = new Random();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        //long startTime = System.nanoTime();
        
        primes = sieveOfEratosthenes(1000000);
        //String output = "";

        while (n > 0){
            out.println(algorithm(sc.nextLong()));
            //out.println(algorithm(rd.nextInt()));
            //output += algorithm(rd.nextInt()) + "\n";
            //output += algorithm(sc.nextLong()) + "\n";
            n--;
        }
       // out.println(output.substring(0,output.length()-1));

        
        //long newTime = System.nanoTime() - startTime;
        //out.println("Total execution time in ms: " + (double)newTime/1000000);
        out.close();
    }

    //DO NOT TOUCH!!! QUIK INPUT / OUTPUT AREA ONLY:

    public static PrintWriter out;
    public static class MyScanner {
       BufferedReader br;
       StringTokenizer st;
  
       public MyScanner() {
          br = new BufferedReader(new InputStreamReader(System.in));
       }
  
       String next() {
           while (st == null || !st.hasMoreElements()) {
               try {
                   st = new StringTokenizer(br.readLine());
               } catch (IOException e) {
                   e.printStackTrace();
               }
           }
           return st.nextToken();
       }
  
       int nextInt() {
           return Integer.parseInt(next());
       }
  
       long nextLong() {
           return Long.parseLong(next());
       }
  
       double nextDouble() {
           return Double.parseDouble(next());
       }
  
       String nextLine(){
           String str = "";
       try {
          str = br.readLine();
       } catch (IOException e) {
          e.printStackTrace();
       }
       return str;
       }
 
    }
}