该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

质数终点

题目描述

Y 同学得到一个整数 $n$。

每次操作时，他可以选择当前整数 $n$ 的任意一个正因数 $x$，并将 $n$ 修改为$\dfrac{n}{x}$;

也就是如下操作:

$n\leftarrow \dfrac{n}{x}$。

Y 同学可以进行任意次操作，直到当前的 $n$ 为质数为止。

请你求出，至少需要进行多少次操作，才能使 $n$ 变为一个质数。

质数是指大于 $1$，并且正因数只有 $1$ 和它本身的整数。

输入格式

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

输出格式

输出一行一个整数，表示使 $n$ 变为质数所需的最少操作次数。

样例

样例输入 #1

8

样例输出 #1

1

样例输入 #2

5

样例输出 #2

0

数据范围与约定

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

• 特殊性质 A：保证 $n$ 为质数。
• 特殊性质 B：保证 $n$ 为偶数。
• 特殊性质 C：保证 $n=p^2$，其中 $p$ 为质数。