题目描述

给定正整数 $n$，现在有 $1,2,\ldots,n$ 共计 $n$ 个整数。你需要从这 $n$ 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也即最大公约数为 $1$）。

请问，最多可以选取多少个整数？

输入格式

输入一行，一个正整数 $n$。

输出格式

输出一行，一个正整数，表示最多可以选取的整数个数。

样例

6

4

样例解释

在 $1$ 到 $6$ 中，最多可以选择 $4$ 个整数，例如 $\{1,2,3,5\}$ 或 $\{1,3,4,5\}$ 等。

数据范围

对于 $100\%$ 的测试点，保证 $1 \le n \le 10^5$。