'''
cache = {}

def binomcoeffb(n,k):
    nom = 1
    denum = 1
    for i in range(n-k):
        nom *= (n-i)
        denum *= (i+1)
    v = nom//denum
    cache[(n,k)] = v
    return v

def binomcoeffc(n,k):
    if (n,k) in cache:
        return cache[(n,k)]
    if n == k or k == 0:
        return 1
    v = binomcoeffc(n-1,k-1) + binomcoeffc(n-1,k)
    cache[(n,k)] = v
    return v

def binomcoeff(n,k):
    try:
        v = binomcoeffc(n,k)
    except RuntimeError:
        v = binomcoeffb(n,k)
    return v

def binomcoeffi():
    l = [1,2,1]
    i = 3
    yield (i,l[1:-1])

    while True:
        i += 1
        nl = [1]
        for j in range(len(l)-1):
            nl.append( l[j]+l[j+1] )
        nl.append(1)
        l = nl
        yield (i,l[1:-1])

def is_prime(n):
    if n <= 1:
        return False
    for n
        bc = binomcoeff(n,k)
        r = bc % n
#        print("%d %% %d = %d" % (bc,n,r))
        if r != 0:
            return False
    return True
'''
class PrimeGenerator:
    def __init__(self):
        self.coeffs = [1,1]
        self.prime = 1

    def nextPrime(self):
        self.step()
        while not self.check():
            self.step()
        return self.prime

    def step(self):
        l = [1]
        for j in range(len(self.coeffs)-1):
            l.append(self.coeffs[j] + self.coeffs[j+1])
        l.append(1)
        self.coeffs = l
        self.prime += 1

    def check(self):
        for i in range(1,len(self.coeffs)//2+1):
            if self.coeffs[i] % self.prime != 0:
                return False
        return True


pg = PrimeGenerator()

for i in range(10001):
    print("%d: %d" % (i,pg.nextPrime()) )