Encryption Key

Interview

Time limit2sMemory limit128 MB

Summary

Determine for each large number S whether all its prime factors exceed one million, using trial division up to that bound.

Level: Easy3 of 10
Topics: Number theory, Math, Brute force
Solved: No attempts yet

Problem

Many modern cryptographic systems use a number formed by multiplying very large prime numbers as an encryption key, because factoring a very large number quickly is practically hard.

In practice these primes have hundreds of thousands of digits or more, but here we work at a smaller scale: we treat any prime greater than $1{,}000{,}000 = 10^6$ as a "very large prime."

Given a number $S$ , write a program that decides whether it is a good encryption key at this scale. $S$ is a good encryption key if every prime factor of $S$ is greater than $10^6$ ; otherwise it is not.

Input

The first line contains the count of numbers, $N$ . Each of the next $N$ lines contains one number $S$ to be checked.

Output

Print $N$ lines: for each number print YES if it is a good encryption key and NO otherwise, in the order given.

Constraints

$1 \le N \le 10$
$10^{12} \le S \le 10^{18}$

Examples1

Example 1

Input

3
1000036000099
1500035500153
20000000000002

Expected output

YES
NO
NO