Вам дано целое число n.

Найдите количество чисел от 1 до n, которые имеют чётное количество делителей.

Входные данные
В первой строке одно целое число n (1≤n≤10⁹).

Выходные данные
Выведите ответ.

Система оценки
Данная задача содержит 10 тестов. Каждый тест оценивается в 10 баллов:
1≤n≤1000. Тесты с номерами 1-6.
1≤n≤10⁵. Тесты с номерами 7-8.
1≤n≤10⁹. Тесты с номерами 9-10.

Примечание
В примере:
У числа 1 делители: 1. Количество 1 — нечётно.
У числа 2 делители: 1, 2. Количество 2 — чётно.
У числа 3 делители: 1, 3. Количество 2 — чётно.
У числа 4 делители: 1, 2, 4. Количество 3 — нечётно.
У числа 5 делители: 1, 5. Количество 2 — чётно.
У числа 6 делители: 1, 2, 3, 6. Количество 4 — чётно.
У числа 7 делители: 1, 7. Количество 2 — чётно.
У числа 8 делители: 1, 2, 4, 8. Количество 4 — чётно.
У числа 9 делители: 1, 3, 9. Количество 3 — нечётно.
У числа 10 делители: 1, 2, 5, 10. Количество 4 — чётно.

Примеры
входные данные
10
выходные данные
7

0 0 Пожаловаться