008 - マリア・アントーニア・ヨーゼファ・ヨハンナ・フォン・ハプスブルク＝ロートリンゲン (Maria Antonia Josepha Johanna von Habsburg-Lothringen)

Aphorismus

問題

あなたはマリア・アントーニアです。
革命が起き、あなたは処刑されることになりました。
しかし、

と考えたので、受け入れることにしました。
さて、処刑まではN日あります。
暇なのでゲームをすることにしました。
1~Nまでの数字が一つ書かれた、表と裏が区別できるカードを一枚ずつ用意します。
初めは全て表にしておきます。 1日目にはこれらのカードのうち1の倍数が書かれたカードをひっくり返します。
2日目にはこれらのカードのうち2の倍数が書かれたカードをひっくり返します。
i日目にはこれらのカードのうちiの倍数が書かれたカードをひっくり返します。
この動作を処刑の日まで繰り返したとき、最終的に表になっているカードは何枚あるでしょうか。

入力

N

出力

ans

制約

$1$ ≤ $N$ ≤ $10$⁶

テストケース

例1

入力

3

出力

2

iが書かれたカードが表の時、裏の時をそれぞれH[i], T[i]と表すと
1日目は T[1], T[2], T[3]
2日目は T[1], H[2], T[3]
3日目は T[1], H[2], H[3]
となります。表——H——なのは2, 3の二枚なので2を出力します。

例2

入力

10

出力

7