Given a positive integer (K > 2), with prime factorization:

    K = p1^a1 * p2^a2 ... * pn^an   (Excluding 1)

Compute the following:

    S = a1*p1 + a2*p2 ... + an*pn.

Input

A integer K on each line (2 <= k <= 10^15).

Take input until EOF has occurred.

Output

For each integer compute the S = a1*p1 + a2*p2 ... + an*pn and output it on a single line.

Example

Input:
6
7
1804289385
846930888
1681692779
1714636917

Output:
5
7
120285967
18767
360709
1008039

WARNING: There are more than 10000 integers in the test file, use I/O optimization too.