Description

给定正整数 n，现在有1,2,3 ...... n  共计 n 个整数。

你需要从这 n 个整数中选取⼀些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最⼤公因数为 1）。

请你最⼤化所选取整数的数量。例如，当 n=9 时，可以选择1,5,7,8,9共计 9 个整数。可以验证不存在数量更多的选取整数的⽅案。

Input Format

⼀⾏，⼀个正整数 n，表⽰给定的正整数。

Output Format

⼀⾏，⼀个正整数，表⽰所选取整数的最⼤数量

6

4

9

5

Hint

对于 40% 的测试点，保证 1<=n<=1000

对于所有测试点，保证 1<=n<=100000

Source