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 example, the subsequences of 1234 having a length 3 are:

• 123
• 124
• 234
• 134

Example

Input:
2
141
18567

Output:
NO
YES

For the second test case, we can choose the subsequences, 157, 167 etc which are prime