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.math.BigInteger;
			import java.util.*;
				
				
				public class Practice {
					private static InputStream stream;
					private static byte[] buf = new byte[1024];
					private static int curChar;
					private static int numChars;
					private static SpaceCharFilter filter;
					private static PrintWriter pw;
					private static long mod=1000000009;
				
				    public static void main(String[] args) {
				    	InputReader(System.in);
						pw = new PrintWriter(System.out); 
				        new Thread(null ,new Runnable(){
				           public void run(){
				               try{
				                   solve();//This is solution method
				                   pw.close();
				               } catch(Exception e){
				                   e.printStackTrace();
				               }
				           }
				       },"1",1<<26).start();
				   }
				    
				    
				    
				    static HashSet<Integer> hs=new HashSet<Integer>();
				    private static void solve() throws NumberFormatException, IOException{
				    	BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

				    	/*boolean prime[]=new boolean[10000001];
				    	Arrays.fill(prime, true);
				    	int spf[]=new int[10000001];
				    	for(int i=2;i<=10000000;i+=2)
				    	{
				    		if(i!=2)
				    			prime[i]=false;
				    		spf[i]=2;
				    	}
				    	for(int j=3;j*j<=10000000;j+=2){
				    		
				    		if(prime[j]){
				    			spf[j]=j;
				    			for(int i=2;i*j<=10000000;i++){
				    				if(prime[i*j]){
				    				prime[i*j]=false;
				    				spf[i*j]=j;}
				    			}
				    		}
				    	}
				    	*/
				    	
				    	
				    	int n=nextInt();
				    	while(n-->0){
				    		long t=nextLong();
				    		long sq=(long)Math.sqrt(t);
				    		if(sq*sq==t){
				    			if(isPrime(sq))
				    				pw.println("YES");
				    			else
				    				pw.println("NO");
				    		}else{
				    			pw.println("NO");
				    		}
				    	}
				    	pw.close();
				}
				   
				    
				    
				    private static BigInteger ncr(int n,int k){
				    	if (k < 0 || k > n) return BigInteger.ZERO;
				        if (n-k < k) k = n-k;
			
				        BigInteger x = BigInteger.ONE;
				        for (int i = 1; i <= k; i++) {
				            x = x.multiply(new BigInteger(""+(n-i+1)));
				            x = x.divide(new BigInteger(""+i));
				        }
			
				return x;
				    }
				    static long fact[];
				private static void factmod(int n,int mod){
					fact=new long[n+1];
					fact[0]=1;
					for(int i=1;i<=n;i++){
						fact[i]=i*fact[i-1];
						//fact[i]%=mod;
				
					}
					
				}
				private static long phi(long n){
					long ans=n;
					if(n%2==0)
						ans-=(ans/2);
					while(n%2==0)
					{
						n/=2;
						
					}
					for(int i=3;i*i<=n;i+=2){
						if(n%i==0){
						while(n%i==0){
							n/=i;
						}
						ans-=(ans/i);
						}
					}
					if(n>2)
						ans-=(ans/n);
					
					return ans;
				}
				static long d,x,y;
				static long modInverse(long A, long M)
				{
				extendedEuclid(A,M);
				return (x%M+M)%M;    //x may be negative
				}
				static void extendedEuclid(long A, long B) {
				if(B == 0) {
				d = A;
				x = 1;
				y = 0;
				}
				else {
				extendedEuclid(B, A%B);
				long temp = x;
				x = y;
				y = temp - (A/B)*y;
				}
				}
				static boolean prime[];
				public static void sieve(int n){
					prime=new boolean[n+1];
					for(int i=4;i<=10000000;i+=2)
						{
						if(i>1000000){
							hs.add(i);
						}
						else
						prime[i]=true;
						}
					
					for(int i=3;i*i<=10000000;i+=2){
						
						if((i<=1000000 && prime[i]==false) || (i>1000000 && !hs.contains(i))){
							for(int j=2*i;j<=n;j+=i)
								if(j<=1000000)
								prime[j]=true;
								else
									hs.add(i);
						}
					}
					
				}
				public static boolean isPrime(long n) {
					
					if (n <= 1)
						return false;
					if (n <= 3)
						return true;
				
					if (n % 2 == 0 || n % 3 == 0)
						return false;
				
					for (long i = 5; i * i <= n; i = i + 6)
						if (n % i == 0 || n % (i + 2) == 0)
							return false;
				
					return true;
				}
				
				    public static long pow(long n, long p,long mod) {
						if(p==0)
							return 1;
						if(p==1)
							return n%mod;
						if(p%2==0){
							long temp=pow(n, p/2,mod);
						return (temp*temp)%mod;
						}else{
							 	long temp=pow(n,p/2,mod);
							 	temp=(temp*temp)%mod;
							 	return(temp*n)%mod;
							 	
						}
					}
					public static long gcd(long x, long y) {
						if (x == 0)
							return y;
						else
							return gcd( y % x,x);
					}
					
					
					public static void InputReader(InputStream stream1) {
						stream = stream1;
					}
				 
					private static boolean isWhitespace(int c) {
						return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
					}
				 
					private static boolean isEndOfLine(int c) {
						return c == '\n' || c == '\r' || c == -1;
					}
				 
					private static int read() {
						if (numChars == -1)
							throw new InputMismatchException();
						if (curChar >= numChars) {
							curChar = 0;
							try {
								numChars = stream.read(buf);
							} catch (IOException e) {
								throw new InputMismatchException();
							}
							if (numChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
				 
					private static int nextInt() {
						int c = read();
						while (isSpaceChar(c))
							c = read();
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = read();
						}
						int res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = read();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
				 
					private static long nextLong() {
						int c = read();
						while (isSpaceChar(c))
							c = read();
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = read();
						}
						long res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = read();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
				 
					private static String nextToken() {
						int c = read();
						while (isSpaceChar(c))
							c = read();
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = read();
						} while (!isSpaceChar(c));
						return res.toString();
					}
				 
					private static String nextLine() {
						int c = read();
						while (isSpaceChar(c))
							c = read();
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = read();
						} while (!isEndOfLine(c));
						return res.toString();
					}
				 
					private static int[] nextIntArray(int n) {
						int[] arr = new int[n];
						for (int i = 0; i < n; i++) {
							arr[i] = nextInt();
						}
						return arr;
					}
				 
					private static int[][] next2dArray(int n, int m) {
						int[][] arr = new int[n][m];
						for (int i = 0; i < n; i++) {
							for (int j = 0; j < m; j++) {
								arr[i][j] = nextInt();
							}
						}
						return arr;
					}
					private static char[][] nextCharArray(int n,int m){
						char [][]c=new char[n][m];
						for(int i=0;i<n;i++){
							String s=nextLine();
							for(int j=0;j<s.length();j++){
								c[i][j]=s.charAt(j);
							}
						}
						return c;
					}
				 
					private static long[] nextLongArray(int n) {
						long[] arr = new long[n];
						for (int i = 0; i < n; i++) {
							arr[i] = nextLong();
						}
						return arr;
					}
				 
					private static void pArray(int[] arr) {
						for (int i = 0; i < arr.length; i++) {
							pw.print(arr[i] + " ");
						}
						pw.println();
						return;
					}
				 
					private static void pArray(long[] arr) {
						for (int i = 0; i < arr.length; i++) {
							pw.print(arr[i] + " ");
						}
						pw.println();
						return;
					}
				 
					private static void pArray(boolean[] arr) {
						for (int i = 0; i < arr.length; i++) {
							pw.print(arr[i] + " ");
						}
						pw.println();
						return;
					}
				 
					private static boolean isSpaceChar(int c) {
						if (filter != null)
							return filter.isSpaceChar(c);
						return isWhitespace(c);
					}
				 
					private interface SpaceCharFilter {
						public boolean isSpaceChar(int ch);
					}
				
					
				}	
				
				class Pair implements Comparable<Pair>{
					
					int city,pop;
					Pair(int city,int pop){
						this.city=city;
						this.pop=pop;
					}
					@Override
					public int compareTo(Pair o) {
				return pop-this.pop;
				
					}
					public int hashCode() {
							int hu = (int) (city ^ (city >>> 32));
							int hv = (int) (pop ^ (pop >>> 32));
							//int hw = (int) (mass ^ (mass >>> 32));
							return 31 * hu + hv ;
						//return 0;
						}
						public boolean equals(Object o) {
							Pair other = (Pair) o;
							return city == other.city && pop == other.pop;
						}
				}