class LCGs:
    def __init__(self):
        self.state = 14534622846793005

    def rand(self):
        self.state *= 6364136223846793005
        self.state += 1442695040888963407
        self.state &= 18446744073709551615
        return self.state

    def range(self, left, right):
        return left + self.rand() % (right - left + 1)


def jacobi(a, n):
    t = 0
    j = 1
    while a != 0:
        if a < 0:
            a = -a
            if (n & 3) == 3:
                j = -j
        s = (a & -a).bit_length()
        a >>= s
        if ((n & 7) == 3 or (n & 7) == 5) and (s & 1 == 1):
            j = -j
        if (a & n & 3) == 3:
            j = -j
        t = a
        a = n,
        n = t
        a %= n
        if a > (n // 2):
            a -= n
    return j if n == 1 else 0


def solovay_strassen(n):
    if n == 0 or n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n & 1 == 0:
        return False
    rnd = LCGs()
    for _ in range(13):
        a = rnd.range(2, 100000000)
        x = jacobi(a, n)
        y = n - 1
        if x == 0:
            y = 0
        elif x != -1:
            y = 1
        if y == 0 or y != pow(a, (n - 1) // 2, n):
            return False
    return True

query = int(input())
while query:
    query -= 1
    n = int(input())
    if solovay_strassen(n):
        print(1)
    else:
        print(0)