Primality Test

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 5305    Accepted Submission(s): 2464

 

Problem Description A positive integer is called a prime if it is greater than 1 and cannot be written as the product of two smaller positive integers. A primality test is an algorithm for determining whether an input number is a prime. For example, the Miller-Rabin primality test is a probabilistic primality test. This problem is precisely the one about the primality test.

Let's define the function f(x) as the smallest prime which is strictly larger than x. For example, f(1)=2, f(2)=3, and f(3)=f(4)=5. And we use ⌊x⌋ to indicate the largest integer that does not exceed x. 

Now given x, please determine whether g(x) is a prime.
  g(x)=⌊f(x)+f(f(x))2⌋  

Input The first line of the input contains an integer T (1≤T≤105), indicating the number of test cases.

Each test case contains an integer x (1≤x≤1018) in a single line.  

Output For each test case, if g(x) is a prime, output 횈홴횂 in a single line. Otherwise, output 홽홾 in a single line.  

Sample Input

2 1 2  

Sample Output

YES NO  

Hint
When x=1, f(x)=2, f(f(x))=f(2)=3, then g(x)=⌊2+32⌋=2, which is a prime. So the output is 횈홴횂.

When x=2, f(x)=3, f(f(x))=f(3)=5, then g(x)=⌊3+52⌋=4, which is not a prime. So the output is 홽홾.

#include 
#include 
using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        long long x;
      scanf("%lld", &x);
        if (x == 1){
            puts("YES");
        } else {
            puts("NO");
        }
    }
    return 0;
}