29525번 - Зелье <<Фи>> 다국어

문제

На полпути к замку Темного Властелина сэр Петрейн подумал, что негоже идти в гости с пустыми руками. В связи с этим он заглянул к одной своей знакомой ведьме и спросил у нее, что бы такого преподнести Темному Властелину. Ведьма предложила приготовить зелье <<Фи>>. Главным ингредиентом этого зелья является кора Темных Дубов, растущих в Темной Роще. Однако не все дубы в Темной Роще --- Темные Дубы. А для зелья нужно собрать кору со всех Темных Дубов в Темной Роще.

Вспомнив о том, какие химеры живут в Темном Лесу, можно догадаться, что Темный Властелин --- большой любитель математики. В Темной Роще $n - 1$ дуб, и дубы пронумерованы целыми числами от 2ドル$ до $n$. Причем Темными Дубами являются те дубы, номерами которых являются такие $x,ドル что $x$ делится на количество чисел от 1ドル$ до $x,ドル взаимно простых с $x$ (числа $a$ и $b$ являются взаимно простыми, если их единственным общим делителем является единица). Например, дуб с номером 6ドル$ является Темным Дубом, потому что количество чисел от 1ドル$ до 6ドル,ドル взаимно простых с 6ドル,ドル равно 2ドル$ (это числа 1ドル$ и 5ドル$), и 6ドル$ делится на 2ドル$. А дуб с номером 10ドル$ не является Темным Дубом, поскольку с 10ドル$ взаимно просты 4ドル$ числа до 10ドル$ (1ドル,ドル 3ドル,ドル 7ドル$ и 9ドル$), а 10ドル$ не делится на 4ドル$.

Сэр Петрейн отправил собирать кору своего оруженосца. Тот решил купить телегу для погрузки в нее коры. Причем не слишком большую, чтобы она была не слишком дорога, и не слишком маленькую, чтобы кора в нее влезла. Для этого нужно заранее выяснить, со скольких дубов нужно собрать кору. Помогите это узнать.

입력

Во входном файле записано единственное целое число $n$ (2ドル \le n \le 10^{18}$).

출력

В выходной файл выведите количество дубов, с которых придется обдирать кору оруженосцу.

제한

힌트