题目描述

小圆学不会除法，上二年级的他某一天突然遇到了一个问题：给你一个整数 $n$，你可以任选出 $n$ 的一个因子 $x$，然后将 $n$ 除以 $x$。小圆需要进行任意次这样的操作，直到 $n$ 是一个质数为止。他想知道的事，至少几次操作可以让 $n$ 变成一个质数。

由于小圆不会除法，更不知道因子是什么，所以他把这个问题留给了你，由你来帮他解决这个问题。

例如：原来的数字 $n=8$，选择 $8$ 的一个因子 $2$（$8$ 有 $1,2,4,8$ 四个因子），将 $8$ 除以 $2$，此时 $n=4$。然后再选择 $4$ 的一个因子 $2$，将 $4$ 除以 $2$，得到 $n=2$。此时 $n$ 是一个质数。（这样的操作方案不一定是最优的，因为本题需要求最少的操作次数）

输入格式

输入仅一行一个整数 $n$。

输出格式

输出一行一个答案。

样例 #1

样例输入 #1

8

样例输出 #1

1

样例 #2

样例输入 #2

5

样例输出 #2

0

提示

对于 $20\%$ 的数据，$n\le 1000$；

对于 $80\%$ 的数据，$n\le 10^6$；

对于 $100\%$ 的数据，$2\le n\le 10^{10}$