URI Online Judge | 3002

Save Lilly!

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

Lilly lives in a country where her government charges her many taxes. In this country, the rule is: if your income is N, you will have to pay the value of the largest N divisor in taxes. For example, if N is 25, you will have to pay 5 for taxes, if for 2, you will have to pay 1.

Lilly is clever, as the saying goes, the world is the smart one, and will divide her income in separate quantities, so that the sum of each part equals N, and thus be able to pay less taxes. For example, if she has 24 of income and will divide into parts being 20, and 4, she will have to pay the sum of the highest divisor of each, which in this case is 10 + 2 = 12, which is not necessarily better division in as many parts as possible.

After a long programming marathon, Lilly has to pay her taxes this very day, but she has no time to figure out a way to minimize the amount she will have to pay, so she asked you to create a program that calculates this amount. Portions of size 1 are not possible as it would be very obvious to the government that Lilly is cheating.


Contains an N (2 ≤ N ≤ 2 * 109).


An integer representing the minimum total tax Lilly will pay.

Input Samples Output Samples