eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найменша сума НСК

Найменша сума НСК

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

НСК (найменше спільне кратне) множини цілих чисел визначається як найменше число, що ділиться на кожне число із цієї множини. Цікаво помітити, що довільне натуральне число може бути виражене як НСК деякої множини натуральних чисел. Наприклад, 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 (1n2^311). Останній тест містить n = 0 і не обробляється.

Вихідні дані

Для кожного тесту в окремому рядку надрукувати його номер у форматі "Case #: " (# - номер тесту). Після чого слід вивести найменше значення суми елементів шуканої множини.

Приклад

Вхідні дані #1
12
10
5
0
Вихідні дані #1
Case 1: 7
Case 2: 7
Case 3: 6