Shubham has fallen in love with prime numbers. He has recently started researching more about it. No, in his research he needs to check whether a given number is prime or not. Help him perform this trivial task as fast as possible.

Input Format
The first line contains T, the number of testcases. Then T lines follow. Each line contains a single integer N.

Output Format
Output consists of T lines where each line consists of True if N is a prime number or False if N is a composite number.

Constraints
$1 \le T \le 10^6$
$0 \le N \le 10^6$