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}$).

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