1063 - 課程主義

問題

r1825はei1821と次のようなゲームで遊びます。

1. 1からNまでの番号が書かれた裏表が区別できるカードを用意し、全て場に表側に置きます。
2. r1825は、1からNの中でまだ言われたことのない数字を一つ言います。
3. ei1821は、1からNまでのカード全て見て、もし書かれた数字がr1825が言った数字の倍数だったらひっくり返します。
4. 1からNまでの数字が全て言われたら終了し、まだならr1825とei1821を入れ替えて2に戻ります。

このようにしたあと、ふたりは表面になっているカードを可能な限り多くしたいです。
2人が最適に行動した場合、表面になっているカードは何枚になりますか。

入力

N

出力

ans

制約

テストケース

例1

入力

3

出力

2

まずr1825が「2」を宣言します。
このとき「2」が裏になります。
次にei1821が「3」を宣言します。
このとき、「3」が裏になります。
最後にr1825が「1」を宣言します。
このとき、「1」が裏になりますが、「2」と「3」が表になります。
よって、答えは「2」です。

例2

入力

10

出力

7