AUCSE015 - Contains Prime

no tags 

We will try investigating if a number contains a prime within it.

Input

The first line contains an integer T(1 <= T <= 100) which denotes the number of test cases.

Each test case contains a single integer N(100 <= N <= 1000000000).

Output

For each test case print "YES" if its possible to choose a subsequence of length 3 of the number which is a prime else print "NO" (without quotes).

Note: Consider the given number as a string of digits. So subsequences of this number refer to the numbers that can be formed by deleting zero or more digits from the original number and concatenating the left ones.

For eg,

Subsequence of 1234 having a length 3 are,

123

124

234

134

Example

Input:
2
141
141
18567
18567 Output: NO
YES
For the second test case, we can choose the subsequences, 157, 167 etc which are prime

hide comments
Mitch Schwartz: 2011-11-03 19:34:09

Got AC under assumption that leading zeroes are allowed in subsequences.


Added by:amit karmakar
Date:2011-08-07
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64