function pow_mod(a, k, m)
    ret = 1
    b = a
    deg = k
    while deg > 0 do
        if (deg % 2) == 1 then
            ret = ret * b % m
        end
        b = b * b % m
        deg = deg / 2
    end
    return ret
end

function miller_rabin(n, bases)
    d, s = n - 1, 0
    while d % 2 == 0 do
        d = d / 2
        s = s + 1
    end
    for i, base in ipairs(bases) do
        if n <= base then
            return true
        end
        a = pow_mod(base, d, n)
        if a == 1 then
        else
            r = 1
            while a ~= n - 1 do
                if r == s then
                    return false
                end
                a = a * a % n
                r = r + 1
            end
        end
    end
    return true
end

function is_prime(n)
    if n <= 1 then
        return false
    end
    if n == 2 or n == 3 or n == 5 or n == 7 then
        return true
    end
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 then
        return false
    end
    if n < 121 then
        return true
    end
    if n < 4759123141 then
        return miller_rabin(n, {2, 7, 61})
    end
    return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022})
end

local n = io.read("*n")

while n > 0 do
    n = n - 1
    local x = io.read("*n")
    io.write(x)
    io.write(" ")
    if is_prime(x) then
        print("1")
    else
        print("0")
    end
end