def enumerate_primes(n: int) -> list:
    """エラトステネスの篩 計算量O(NloglogN)
    https://mikan-alpha.hatenablog.com/entry/2020/07/29/210342"""
    assert n >= 1
    isp = [True] * (n+1 >> 1)
    for i in range(3, int(n**0.5)+1, 2):
        if isp[i >> 1]:
            isp[i*i >> 1::i] = [False] * int(((n-1 >> 1)-(i*i >> 1))//i+1)
    return [2]*int(n != 1) + [(i << 1)+1 for i in range(1, n+1 >> 1) if isp[i]]


primes = enumerate_primes(10**5)
n = int(input())
for i in range(n):
    x = int(input())
    print(x, int(x in primes))