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

题目描述

学生丹丹学不会除法， 有一天他遇到了这样的一个问题： 给定一个整数 $n$，你可以任选一个 $n$ 的因子 $x$，然后将 $n$ 除以 $x$。你可以进行任意次这样的操作，直到 $n$ 是一个质数为止。请问至少几次操作可以让 $n$ 变成一个质数。

由于丹丹不会除法， 更不知道因子是什么意思， 所以他将这个问题交给你了， 请你帮他解决这个问题。

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

输入格式

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

输出格式

输出一行一个答案。

样例 1 输入

8

样例 1 输出

1

样例 1 说明

选择 $8$ 的因子 $4$，将 $8$ 除以 $4$，得到 $2$ ，$2$ 是质数，共用了一次操作。

样例 2 输入

5

样例 2 输出

0

样例 2 说明

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

数据范围

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

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