Special Friends of Two

NSU Inter University Prog...
Limits 5s, 512 MB

Let's consider two positive numbers X and Y to be friends if

    - X and Y have same length and differ in exactly one digit. e.g. 11 - 31
    - Adding one digit to the left of X (or Y) makes Y (or X). e. g. 11 - 211

Since 2 is my favorite number, we'll consider any number P to be special if

    - P is a prime number and friend of 2.
    - There exists a chain of connected primes between 2 and P.
    - No prime in the chain exceeds P.

For example, 4127 is special. One of the possible chain is:

2 -> 3 -> 13 -> 113 -> 103 -> 107 -> 127 -> 4127

Your task is to find whether a number is special or not.

Input

There are several test cases T (1 < T ≤ 105). For each case, you'll be given one integer N (1≤N≤107).

Output

For each test case, print "YES" if the number is special, "NO" otherwise. Check the sample output for details.

Sample

InputOutput
4
2
103
113
4127
YES
NO
YES
YES

Submit

Login to submit.

Statistics

25% Solution Ratio
mahbubcsejuEarliest, Feb '17
mahbubcsejuFastest, 891784.5s
imranziadLightest, 27 MB
mahbubcsejuShortest, 2624B
Toph uses cookies. By continuing you agree to our Cookie Policy.