from crivo import *

lista_de_primos = crivo(10**5)

def Carmichael(n):
    if n in lista_de_primos:
        return False

    m = n

    for primo in lista_de_primos:
        if m % primo == 0:
            m //= primo
            if m % primo == 0 or (n-1) % (primo-1) != 0:
                return False
            if m == 1:
                return True

x = 1
for n in range(3,10**5):
    if Carmichael(n):
        print(x,n)
        x += 1