#!/usr/bin/python

# https://projecteuler.net/problem=12
# The sequence of triangle numbers is generated by adding the natural numbers.
# So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first
# ten terms would be:

# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

# Let us list the factors of the first seven triangle numbers:

#  1: 1
#  3: 1,3
#  6: 1,2,3,6
# 10: 1,2,5,10
# 15: 1,3,5,15
# 21: 1,3,7,21
# 28: 1,2,4,7,14,28

# We can see that 28 is the first triangle number to have over five divisors.

# What is the value of the first triangle number to have over five hundred
# divisors?

# Answer:


import sys


def triangle_numbers():
    accumulator = 0
    i = 1
    while True:
        accumulator += i
        i += 1
        yield accumulator


def get_factors_o(n):
    result = set()
    result.add(1)
    result.add(n)
    for i in range(2, n/2 + 1):
        if n % i == 0:
            result.add(i)
            result.add(n/i)
    return result


def get_factors(n, memo):
    result = set()
    for i in range(1, n/2 + 1):
        if n % i == 0:
            if n/i in memo:
                # print 'hit'
                result = result.union(memo[n/i])
                break
            else:
                # print 'miss'
                result.add(i)
                result.add(n/i)
    memo[n] = result
    return result



if __name__ == '__main__':
    n = int(sys.argv[1])

    memo = dict()
    maxcount = 0

    for t in triangle_numbers():

        count = len(get_factors(t, memo))
        if count > maxcount:
            maxcount = count
            print str(t) + ': %s factors' % count
        # print memo
        if count > n:
            print str(t) + ': %s factors' % count
            break