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

题目描述

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

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

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

输入描述

输入仅一行一个整数 。

输出描述

输出一行一个答案。

示例1

8

1

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

示例2

5

0

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

输入输出备注

对于 80% 的数据，有

对于 100% 的数据，有