import random
import math


def judge_miller(val):
    if(val == 1):
        return False
    if(val == 2):
        return True
    if(val % 2 == 0):
        return False
    for k in range(100):
        a = random.randint(2, val-1)
        if(math.gcd(a, val) != 1):
            return False
        x = val - 1
        is_prime = False
        while(x % 2 == 0):
            m = pow(a, x, val)
            if(m % val == val-1):
                is_prime = True
            x = int(x/2)
        m = pow(a, x, val)
        if(m % val == 1 or m % val != val-1):
            is_prime = True
        if(is_prime):
            return True
    return False


if __name__ == "__main__":
    x = int(input())
    for i in range(x):
        v = int(input())
        res = judge_miller(v)
        if(res):
            print(str(v)+" 1")
        else:
            print(str(v)+" 0")