Новий алгоритм шифрування#147

Новий алгоритм шифрування

1 second
512 megabytes
Medium

Фірма, на яку влаштовується Степан, займається розробкою нового наднадійного алгоритму шифрування RSA-SUPER. Степан дізнався, що RSA (абревіатура від прізвищ Rivest, Shamir і Adelman) - криптографічний алгоритм з відкритим ключем. Криптосистема RSA стала першою системою, придатною і для шифрування, і для цифрового підпису. Алгоритм використовується у великому числі криптографічних додатків, включаючи PGP, S / MIME, TLS / SSL, IPSEC / IKE та інших.

Як відомо, в основі алгоритму RSA лежить використання пари простих натуральних чисел і і утвореного числа N = P * Q. Числа і називаються ключами шифрування, а число - модулем шифрування. Просте число - це натуральне число, яке має рівно два різних натуральних дільники: одиницю і самого себе.

Принциповою відмінністю нового RSA-SUPER алгоритму від RSA алгоритму полягає у виборі ключів. Якщо в реалізації RSA алгоритму потрібна пара простих чисел і , то в RSA-SUPER алгоритмі числа і повинні бути взаємно простими. Два натуральних числа називаються взаємно простими, якщо вони не мають жодних спільних дільників, крім одиниці.

Для аналізу надійності нового алгоритму власники фірми хочуть дізнатися кількість різних пар ключів і , таких, що 1 < P < Q і відповідний їм модуль шифрування задовольняє умові: N \leq K. Саме це нелегке завдання і було дано Степану, а він, звісно просить допомоги у вас.

Input

Перший рядок вхідного файлу містить одне ціле число (1 \leq K \leq 10^9).

Output

Вихідний файл повинен містити одне ціле число - кількість різних пар ключів і .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі: (2,3); (2,5); (3,4)

У другому прикладі: (2,3); (2,5); (2,7); (2,9); (3,4); (3;5)

Scoring

  • K \leq 300 - не менше 20 балів

  • K \leq 1000 - не менше 30 балів

  • N \leq 5000 - не менше 40 балів

  • N \leq 10^{5} - не менше 50 балів

  • N \leq 10^{6} - не менше 60 балів