题目描述

小码哥学习了一些数学知识，他现在想玩一些数学游戏了。小码哥有$1$到$n$共$n$个数，他想从其中选择一些数，并且要求这些数必须两两互质，他想让选出的数的个数尽可能多，请你帮他算出最多能选多少个数。

输入格式

输入一个整数$n$。

输出格式

输出一个整数，表示你的答案。

样例输入 #1

3

样例输出 #1

3

说明/提示

保证$1\leq n\leq 10^6$。