from math import sqrt
from bisect import bisect_left

def binarySearch(arr, l, r, x):
    while l <= r:
        mid = int(l + (r - l)/2);
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return -1

def sieve_for_primes_to():
    n = 1000000
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

primes = sieve_for_primes_to()

def find_ge(a, key):
    i = bisect_left(a, key)
    return a[i+1]

def find_next_prime(p):
    return find_ge(primes, p)

def factorize(n):
    distinct_factors = []
    if binarySearch(primes, 0, len(primes)-1, n) == True:
        distinct_factors.append(n)
    else:
        for x in range(2, int(sqrt(n))+1):
            if n % x == 0:
                distinct_factors.append(x)
                if x * x != n:
                    distinct_factors.append(int(n/x))
    return distinct_factors

x = 2
total = 2
used = set({2})
last_output = 0
count_outputs = 1

for t in range(100000):
    x = find_next_prime(x)
    flag = False
    total = sum(used)
    if total != x:
        while total % x == 0:
            remains = factorize(int(total / x))
            for r in remains:
                if r in used:
                    flag = True
                    break
            if flag == True:
                break
            print("Found cyclic", x)
            x = find_next_prime(x)

    total += x

    used.add(x)
    distinct_factors = factorize(total)

    for f in distinct_factors:
        if f in used:
            used.remove(f)
        min_used = min(used)
        if last_output != min_used:
            if (last_output != 0):
                print("{}:".format(last_output), count_outputs)
            count_outputs = 1
            last_output = min_used
        else:
          count_outputs += 1

    x = max(used)