题目描述

给定一个整数 $n$，你可以选择的 $n$ 的任意一个因子 $x$，然后将 $n$ 的值修改为 $n/x$。你可以进行任意次这样的操作，直到 $n$ 是一个质数为止。求：至少几次操作可以让 $n$ 变成质数？

输入格式

一个整数 $n$。

输出格式

一个整数，表示答案。

【数据范围】

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

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