题目背景

渣朱君学不会除法，有一天他遇到了这样的一个问题:

题目描述

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

输入格式

输入仅一行一个整数 n

输出格式

输出一行一个答案。

样例 #1

样例输入 #1

8

样例输出 #1

1

样例 #2

样例输入 #2

5

样例输出 #2

0

提示

【数据范围】

对于 80%的数据，保证 2 ≤ n ≤ 1e6

对于 100%的数据，保证 2 ≤ n ≤ 1e12