Problem G
Vittu betur

The last round of the new trivia contest between universities in the capital area of Iceland is closing in. In this contest the universities answer once and for all who has the brightest students. All questions in the contest all questions pertain to the prime factorizations of numbers and all guessing is disallowed. You were chosen to compete as part of a team for The University of Iceland as soon as word gor out that a relative of yours was making the questions for the contest. Once you went to interrogate your relative he replied ‘All the numbers that I will be asking you to factor will be of the forn $n!$ where $n$ is a positive integer less than or equal to $10^6$. How does this help though? Are you going to memorize all the answers before the contest?’. That is exactly what your team is going to do. Though, first, you have to obtain all the answers so you have to write a program that can factorize $n!$ for a given $n$.

Input

The input consists of a number of lines each containing a single integer $0 \leq n \leq 10^6$. There will at most $10^5$ lines in the input.

Output

The organizers at the tv station hosting the contest didn’t quite like how long the answers could get and thus asked your relative to pick some smaller numbers. As a compromise they decided it would be enough to answer how many prime factors the number has, counted with multiplicities. More specifically, for a given $n$ in the input one can write $n! = \prod {i = 0}^ k p_ i^{e_ i}$ where $p_ i$ is a prime number for all $i$ and the desired output is then $\sum _{i = 0}^ k e_ i$ printed on its own line.

1
2
3
4
5
6
7
8
9
10

0
1
2
4
5
7
8
11
13
15