Description

陆历川很热爱数学，最近他学了质数，他被质数深深的吸引了，但是陆历川有个习惯，他喜欢给一些东西编号，所以他决定给所有的质数编号，例如给2编号1，3编号2，5编号3........这样2，3，5就是质数里面的大当家，二当家和三当家了，陆历川现在知道了这些编号，现在他会给你一个数，他想知道这个数的所有的质因子里面的最大编号是多少？ 注：0和1的编号都是0。

Input

一个自然数$N(0 \leq N \leq 1000000)$ 多组输入样例

Output

最大编号

Sample Input

1
2
3
4
5

Sample Output

0
1
2
1
3