from heapq import heappush, heappop
from itertools import groupby
from time import clock
from math import ceil, sqrt
from itertools import tee


def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


def primes(n):
    "Return all primes <= n."
    sieve = list(range(1, n + 1, 2))
    sieve[0] = 2
    np = len(sieve)
    for i in range(1, (ceil(sqrt(n)) + 1) // 2):
        if sieve[i]:
            p = sieve[i]
            p2 = p * p // 2
            sieve[p2: np: p] = (0,) * len(range(p2, np, p))
    return filter(None, sieve)


def get_exp(n):
    exp = []
    for pi in prime:
        f = 0
        while n % pi == 0:
            f += 1
            n //= pi
        exp.append(f)
        if n == 1:
            break
    return exp


def get_d(n):
    d = 1
    for pi in prime:
        f = 0
        while n % pi == 0:
            f += 1
            n //= pi
        d *= (1 + f)
        if n == 1:
            break
    return d


class NodupQue(object):
    'simple priority que with no duplicates allowed'
    def __init__(self):
        self.__heap = []
        self.__items = set()

    def push(self, item):
        if item not in self.__items:
            self.__items.add(item)
            heappush(self.__heap, item)

    def pop(self):
        item = heappop(self.__heap)
        self.__items.remove(item)
        return item

    def __contains__(self, item): return item in self.__items__
    def __len__(self): return len(self.__heap)
    def __str__(self): return str(self.__heap)


def next_cand(n, Q):
    facs = get_exp(n) + [0]
    Q.push(n * prime[0])
    for j, (ei, ej) in enumerate(pairwise(facs), 1):
        if ei > ej:
            Q.push(n * prime[j])


def encode_hcn(nums):
    'input: prime exponents'
    out = ["(" + str(len(nums)) + ")"]
    for k, g in groupby(nums):
        nk = len(list(g))
        s = str(k) if nk == 1 else "^".join((str(k), str(nk)))
        out.append(s)
    return " ".join(out)


prime = list(primes(10000))
CO = 0.99  # gives correct results at least up to 30000
limit = 2000
# fout = open("hcn2" + str(N) + ".txt", "w")
fmt5 = "{:5d}  {:50s}"
t0 = clock()
Q = NodupQue()
Q.push(1)
maxdivs = 0
i = 0
while True:
    n = Q.pop()
    divs = get_d(n)
    if divs > maxdivs:
        i += 1
        maxdivs = divs
        ss = encode_hcn(get_exp(n))
        print(i, ss)
        # fout.write(fmt5.format(i, ss) + "\n")
        if i == limit:
            break
    if divs / maxdivs > CO:
        next_cand(n, Q)
print("elapsed: {:7.1f} secs".format(clock() - t0))
# your code goes here