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
def len(n):
    l=0
    while n:
        n/=10
        l+=1
    return l

def isprime(n):
    if n==2:
        return 1
    var=None
    for i in xrange(2,n):
        if n%i==0:
            break
        var=i
    if var==n-1:
        return 1
    else:
        return 0

def num_rot(n,f):
    l=len(n)-1
    while f:
        f-=1
        i=n%10
        n/=10
        n+=i*(10**l)
    return n

def cir_prime(n):
    k=n
    l=len(n)
    if isprime(k)==1:
        while l!=0:
            l-=1
            k=num_rot(n,l)
            if isprime(k)!=1:
                break
            if k<n and cir_prime(k)!=0:
                break
        if l==0:
            return 1
        else:
            return 0
    else:
        return 0

t=int(input())
a=raw_input().split(" ")
for j in a:
    print cir_prime(int(j)),