WonderKing himself is a very genius in mathematics. One day when he was thinking, king got a wonderful idea – circular prime. A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will be a prime. Simply if all the rotational digits of a number are themselves primes, it is called a circular prime number.
Let's see an example where numbers are generated by cyclically permuting the digits of 19937. The first digit is removed and readded at the right side of the remaining string of digits. This process is repeated until the starting number is reached again. Since all intermediate numbers generated by this process are prime, 19937 is a circular prime. 19937 is the first circular prime WonderKing encountered.
199379937193719371997199319937
Later he was managed get the first 10 circular primes, they will be 2, 3, 5, 7, 11, 13, 17, 37, 79, 113. You have to help him to find more circular primes.

Input
Input description.
Tips:

The first line of the input contains an integer T denoting the number of test cases, i.e. number of cases you are required to check.
T is followed by the numbers you need to check whether they are circular primes or not

Output
If a certain number is a circular prime print yes. If not a circular prime print no.

Constraints

1 ≤ T ≤ 100
Each and every test case would be less than 1,000,000

Example
Input:
5
3
113
67
9311
19

Output:
Yes
Yes
No
Yes
No

见题面

见题面