9312: 翻转硬币

给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \bmod i=0$ 的位置 $j$ 的硬币翻转。

求最少需要多少次操作可以让所有硬币都朝上。

原题链接：[https://www.luogu.com.cn/problem/P9238](https://www.luogu.com.cn/problem/P9238)


令人感叹洛谷题解代码错了，建议家人们去洛谷提交答案。

输入一行包含一个整数 $n$。

输出一行包含一个整数表示最少需要的操作次数。

## 样例 #1

### 样例输入 #1

```
7
```

### 样例输出 #1

```
6
```

## 样例 #2

### 样例输入 #2

```
1131796
```

### 样例输出 #2

```
688042
```

对于 $30 \%$ 的评测用例，$n \leq 5 \times 10^6$；

对于 $70 \%$ 的评测用例，$n \leq 10^9$；

对于所有评测用例，$1 \leq n \leq 10^{18}$。