010 - 課程主義

時間制限 0.5 秒 / メモリ制限 64 MB / 得点 1 / x 2 /


TLE
0.5sec
MLE
64MB
得点
1

問題

Je le vois, mais je ne le crois pas.
── カントール

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

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

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

入力

N

出力

ans

制約

$1$ ≤ $N$ ≤ $10$18

テストケース

例1

入力

3

出力

2

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

例2

入力

10

出力

7