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

Compute the following:

Input

The integer K on each line (2 ≤ k ≤ 10¹⁵).

Take input until EOF has occurred.

Output

For each integer give the of S.

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.