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 Sample {
		static int k;
		static boolean  sieve[];
		static int MAX = (int)1e7+1;
		static int kk = 0;
		static HashMap<Long,Boolean>map = new HashMap<>();
		static ArrayList<Integer>list = new ArrayList<>();
			public static void main(String[] args) throws Exception{
				Scanner input = new Scanner(System.in);
				int n = input.nextInt();
				long a[] = new long[n];
				StringBuilder sb = new StringBuilder();
				for(int i =0;i<n;i++)a[i] = input.nextLong();
				sieve =new boolean[MAX];
				build();
				for(int i =0;i<n;i++) {
					if(isTPrime(a[i])) {
						sb.append("YES");
						sb.append("\n");
					}else {
						sb.append("NO");
						sb.append("\n");
					}
				}
				System.out.println(sb);
			}
			public static void build() {
				for(int i =2;i*i<MAX;i++) {
					if(!sieve[i]) {
						for(int j = i*i;j<MAX;j+=i) {
								sieve[j] = true;
						}
					}
				}
				for(int i = 2;i<MAX;i++) {
					if(!sieve[i])list.add(i);
				}
				for(long it:list) {
					long ans = it*it;
					map.put(ans,true);
				}
			}
			public static boolean isTPrime(long val) {
				return map.containsKey(val);
				
			}
				
			public static int findMax(int a[]) {
				int max = -1;
				int index = -1;
				for(int i =0;i<a.length;i++) {
					if(a[i]>max) {
						max = a[i];
						index = i;
					}
				}
				return index;
			}
			public static int findMin(int a[]) {
				int min = Integer.MAX_VALUE;
				int index = -1;
				for(int i =0;i<a.length;i++) {
					if(a[i]<min) {
						min = a[i];
						index =i;
					}
				}
				return index;
			}
			
	}