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 prime.[1][2] For example 1193 is a circular prime, since 1931, 9311 and 3119 all are also prime

Input

First line contains an integer N, number of inputs. Second line has space separated N positive integers, none of them greater than 100000

Output
Space separated 0 or 1 values.
Where 0 denote that corresponding number is not circular prime where as 1 indicates it is prime

Example

Input:
10
88 11 2 5 6 9 100 121 233 79

Output:
0 1 1 1 0 0 0 0 0 1

Explanation
11,2,5,79 are circular primes others are not

见题面

见题面