#A064910    Smallest semiprime p1*p2 such that p2 mod p1 = n.
#Python 2.7

from math import sqrt

primes = [2,3,5,7]
def fillprimes(n):
    for i in xrange(9,n,2):
        top = int(sqrt(i)) + 1
        addit = True
        for j in xrange(3,top,2):
            if i % j == 0:
                addit = False
                break
        if addit:
            primes.append(i)

fillarg = 40000
fillprimes(fillarg)

p1start = 0
n = 1
print "0 4"     #p2 = p1 below, so I print this exception here
while n < 10001:
    p1 = p1start
    if primes[p1] < n:
        p1 += 1
        p1start = p1
    p2 = p1+1     #p2 = p1 for n=0, so I print above.
    an = 0
    found = False
    while (not found) or (primes[p1start]*primes[p2] < an):
        if (primes[p2] % primes[p1] == n):
            found = True
            an2 = primes[p2] * primes[p1]
            if (an == 0) or (an2 < an):
                an = an2
            p2 += 1
            p1 = p1start
        else:
            p1 += 1
        if p1 > p2:
            p2 += 1
            p1 = p1start
    print str(n) + " " + str(an)
    n += 1