Q884: Factorial Factors

階層函數 n! = 1^.2^....^.n, 有很多有趣的特性。在這個問題中我們想要知道最多可以用多少整數相乘（1 除外）來表達 n!。例如：

8! = 1^.2^.3^.4^.5^.6^.7^.8 = 2^.3^.2^.2^.5^.3^.2^.7^.2^.2^.2 = 2^{7 .}3^{2 .}5^.7

可以很清楚的觀察到最多可以用 11 個整數（1 除外）相乘來產生 8! 。

Input

輸入含有多組測試資料。

每組測試資料一列有1個整數 n（2 <= n <= 1000000 ）。請參考Sample Input。

Output

對每組測試資料輸出一列。輸出最多可以用多少個整數（1 除外）相乘來產生 n! 。

Sample Input	Sample Output
2 1000000 1996 5 8 123456	1 3626619 5957 5 11 426566