ОЧЕНЬ СРОЧНО!!!!
Вам дано целое число n.

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

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

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

Система оценки
Данная задача содержит 10 тестов. Каждый тест оценивается в 10 баллов:

1≤n≤1000. Тесты с номерами 1-6.
1≤n≤105. Тесты с номерами 7-8.
1≤n≤109. Тесты с номерами 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