Constraints

Time Limit: 1 secs, Memory Limit: 256 MB

Description

In number theory, a positive integer is a semiprime if it is the product of two primes. For example, 35 is a semiprime because 35 = 5 * 7, and both 5 and 7 are primes. A positive integer x is a pseudo semiprime if there is two integers a and b such that a > 1, b > 1, a * b = x, and the greatest common divisor of a and b is 1.

Given an integer x, your task is to find out whether it is a pseudo semiprime.

Input

The input begins with a line containing an integer T (T<=100), which indicates the number of test cases. The following T lines each contain an integer x (1<=x<=1000000000).

Output

For each case, output YES if x is a pseudo semiprime; otherwise output NO.

Sample Input

415810

Sample Output

NONONOYES

Problem Source

SYSUCPC 2014 Preliminary (Online) Round

#include 
  
   
#include 
   
     int gcd(int a, int b) { int temp; while (b) { temp = a % b; a = b; b = temp; } return a; } int main() { int caseNum; scanf("%d", &caseNum); while (caseNum--) { bool isOK = false; int x; scanf("%d", &x); for (int i = 2; i * i <= x; i++) { if (x % i == 0) { if (gcd(i, x / i) == 1) { printf("YES\n"); isOK = true; break; } } } if (!isOK) printf("NO\n"); } return 0; }