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

時間制限 1 秒 / メモリ制限 64 MB / 得点 13 / x 7 /


TLE
1sec
MLE
64MB
得点
13

Aphorismus

あらゆる浪費の中で、最も咎むべきは時間の浪費である。
── マリー・アントワネット

問題

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

犯罪者にとって死刑は恥ずべきものだが
無実の罪で断頭台に送られるなら恥ずべきものではない
── マリー・アントワネット

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

入力

N

出力

ans

制約

$1$ ≤ $N$ ≤ $10$6

テストケース

例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