Скільки натуральних чисел, не більших за \(N\), можна представити у вигляді \(a^2 × b × c^2\) із трьома простими числами \(a\), \(b\) і \(c\), щоб \(a<b<c\)?

Обмеження

• \(N\) є цілим числом, яке задовольняє \(300≤N≤10^{12}\).

Формат вхідних даних

Вхідний потік містить ціле число \(N\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

1000

Приклад вихідних даних

3

Відповідними цілими числами, не більшими за 1000, є наступні три.

• \(300=2^2 ×3×5^2\)
• \(588=2^2 ×3×7^2\)
• \(980=2^2 ×5×7^2\)

Приклад вхідних даних

1000000000000

Приклад вихідних даних

2817785