Minimum Sum LCM#1246
LCM (Least Common Multiple) of a set of integers is defined as the minimum number which is a multiple of all integers in that set. It is interesting to note that any positive integer can be expressed as the LCM of a set of positive integers. For example, 12 can be expressed as the LCM of , ; or , ; or , ; or , ; or , , , ; and so on.
In this problem, you are given a positive integer . You have to find a set of at least two positive integers whose LCM is . As there can be infinitely many such sets, you need to find one with the minimum possible sum of its elements. You are required to print only this minimum sum. For example, for n = 12, you should output 4 + 3 = 7, since the LCM of and is , and is the minimal possible sum.
The input contains at most test cases. Each test case consists of a positive integer (1 \le n \le 2^{31} - 1). Input is terminated by a test case with n = 0, which should not be processed.
For each test case, print its number in the format "Case #: " where # is the test case number. Then print the minimum possible sum of the elements of the required set.
Example 1