Rar the Cat has recently bought a pair of rings for him and his partner! To signify the deep love between them, the sum of all the prime factors of Rar the Cat's ring number will be the number inscribed on his partner's ring. How meaningful!
However, as usual, the careless Rar, in his excitement to propose to his new love, accidentally dropped his partner's ring into the drain. Oh No! Rar the Cat now has no idea what was the original number on his partner's ring. Given the number inscribed on Rar the Cat's ring, help Rar by telling him the new number he should inscribe on his partner's ring.
The input will contain one integer, N, the number on Rar's ring.
The input should end with a newline.
The output should contain one integer, the number that should be inscribed on his partner's ring.
The output should end with a newline.
Subtask 1 (30%): 1 <= N <= 1,000
Subtask 2 (70%): 1 <= N <= 1,000,000
Sample Input 1
Sample Output 1