题目描述

鸡尾酒的学生丹丹学不会除法，有一天他遇到了这样的一个问题：给定一个整数 $n$ ，你可以任选一个 $n$ 的因子 x，然后将 $n$ 除以 x。你可以进行任意次这样的 操作，直到 $n$ 是一个质数为止。请问至少几次操作可以让 $n$ 变成一个质数。 由于丹丹不会除法，更不知道因子是什么意思，所以他将这个问题交给你了，请 你帮他解决这个问题。 例如：原数字 $n = 8$，选择 8 的因子 2，将 8 除以 2，此时 $n = 4$。然后再选择 4 的因子 2，将 4 除以 2，得到 $n = 2$。此时 $n$ 是一个质数。（这样的操作 方案不一定是最优的，因为本题在求最少的操作次数）

输入描述

输入仅一行一个整数 n。

输出描述

输出一行一个答案。

8

1

【样例 1 说明】 选择 8 的因子 4，将 8 除以 4，得到 2，2 是质数，共用了一次操作

5

0

【样例 2 说明】

5 已经是质数了，所以不需要进行任何操作就可以将其变为质数，输出 0。

【数据范围】

对于 $80\%$的数据，有 $2 ≤ n ≤ 10^6$

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