You sleep while we work: due to technical reasons Codeforces may be unavailable on May 22 on time interval 01:00-03:00 (MSK). ×

113. Nearly prime numbers

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

Nearly prime number is an integer positive number for which it is possible to find such primes P1 and P2 that given number is equal to P1*P2. There is given a sequence on N integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.

Input

Input file consists of N+1 numbers. First is positive integer N (1£N£10). Next N numbers followed by N. Each number is not greater than 109. All numbers separated by whitespace(s).

Output

Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case.

Sample Input

1
6

Sample Output

Yes

Author: Michael R. Mirzayanov
Resource: PhTL #1 Training Contests
Date: Fall 2001