Наименьшая сумма НОК
НОК (наименьшее общее кратное) множества целых чисел определяется как наименьшее число, которое делится на каждое число из этого множества. Интересно заметить, что любое натуральное число может быть выражено как НОК некоторого множества натуральных чисел. Например, 12 можно представить как НОК чисел 1, 12, или 12, 12, или 3, 4, или 4, 6, или 1, 2, 3, 4 и так далее.
В задаче задано натуральное число n. Необходимо найти множество, содержащее как минимум два числа, НОК чисел которого равно n. Поскольку таких множеств может быть бесконечное количество, Вам следует найти такое, для которого сумма его элементов минимальна. Мы будем предельно счастливы, если Вы также напечатаете и указанную сумму. Например, для n = 12 необходимо вывести 4 + 3 = 7, так как НОК чисел 4 и 3 равно 12, а 7 - наименьшее возможное значение суммы чисел множества.
Входные данные
Входные данные состоят не более чем из 100 тестов. Каждый тест состоит из натурального числа n (1 ≤ n ≤ 2^31 – 1). Последний тест содержит n = 0 и не обрабатывается.
Выходные данные
Для каждого теста в отдельной строке вывести его номер в формате "Case #: " (# - номер теста). После чего следует вывести наименьшее значение суммы элементов искомого множества.