题目描述

ak机拿到一个整数$x$，并希望通过如下两个操作将$x$变为完全平方数。

1. 如$x$是素数，则将其减1
2. 否则，将其除以自己最小的素因子。

ak机需要操作多少次？

输入描述

一个正整数$x(1\le x\le 10^9)$

输出描述

一个整数，表示操作次数。

样例

输入

5

输出

1

输入

20

输出

3