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.*;

public class Driver230B {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String str=in.nextLine();
        String[] a=str.split(" ");
        long[]abc= new long[a.length];
        long[] nums= new long[a.length];

        for(int i=0;i<a.length;i++){
            nums[i]=Long.parseLong(a[i]);
            abc[i]=Long.parseLong(a[i]);

        }


        Arrays.sort(abc);
        long n=(long)Math.pow(abc[abc.length-1],.5)+1;
        long timeStart= System.currentTimeMillis();
        boolean[] ab=primeList(n);
        long timeEnd=System.currentTimeMillis();
        //System.out.println(timeEnd-timeStart);
        for(long i:nums){
            double sqrt= Math.sqrt(i);
            if(sqrt%1==0){
                if(ab[(int)sqrt]){
                    //System.out.println((System.currentTimeMillis()-x));

                    System.out.println("YES");
                }
                else{
                    System.out.println("NO");

                }
            }
            else{
                System.out.println("NO");
            }

        }


//        for(int i=0;i<nums.length;i++){
//            if(Math.sqrt(nums[i])%1==0){
//                if(nums[i]==1){
//                    System.out.println("NO");
//                }
//                else if(isPrime(Math.sqrt(nums[i]))) {
//                    System.out.println("YES");
//                }else{
//                    System.out.println("NO");
//                }
//
//            }
//            else{
//                System.out.println("NO");
//            }
//        }



    }

//    public static boolean isPrime(double n){
//        if(n<2){
//            return false;
//        }
//        if(n==2){
//            return true;
//        }
//        if(n%2==0){
//            return false;
//        }
//
//        for(int i=3;i<=Math.sqrt(n);i+=2){
//            if(n%i==0){
//                return false;
//            }
//        }
//        return true;
//
//    }
    public static boolean[] primeList(double n){
        ArrayList<Double> a=new ArrayList<Double>();
        boolean[] d;

        d = new boolean[(int) n + 4];


        a.add(2.0);
        for(int i=0;i<n;i++){
            d[i]=true;
        }

        for(int i=4;i<=n;i+=2){
            d[i]=false;
        }
        for(int i=3; i<=n; i+=2){
            if(d[i]){
                for(int j=i*2;j<=n;j+=i){
                    d[j]=false;
                }
            }



//        for(double i=3;i<n;i+=2){
//            boolean b=true;
//            double sqrt=Math.sqrt(i);
//            for(double j = 0; j<a.size(); j++){
//                double k=a.get((int) j);
//                if(i%k==0){
//                    b=false;
//                    j=999999999;
//                }
//                if(k>sqrt){
//                    j=999999999;
//                }
//            }
//            if(b){
//                a.add(i);
//                d[(int)i]=true;
//            }
        }
        d[0]=false;
        d[1]=false;
        d[2]=true;
        d[3]=true;
        return d;
    }
}