B. Волшебные тройки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пока Иэн и Барли ехали по шоссе, чтобы Барли не скучал, Иэн предложил ему посчитать количество волшебных троек. Тройка натуральных чисел $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a \lt b \lt c \le n$$$) называется волшебной, если $$$a \cdot b$$$, $$$a \cdot c$$$ и $$$b \cdot c$$$ — квадраты натуральных чисел.

Помогите Барли решить задачку Иэна, найдите количество волшебных троек.

Входные данные

В единственной строке дано одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$).

Выходные данные

Выведите одно число — количество волшебных троек.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
110$$$n \le 100$$$первая ошибка
220$$$n \le 1\,000$$$1первая ошибка
330$$$n \le 10\,000$$$1, 2первая ошибка
440Без дополнительных ограничений1, 2, 3первая ошибка
Примеры
Входные данные
10
Выходные данные
1
Входные данные
20
Выходные данные
5
Примечание

В первом примере единственной волшебной тройкой является $$$a = 1$$$, $$$b = 4$$$, $$$c = 9$$$.

Во втором примере существуют следующие волшебные тройки:

  • $$$a = 1$$$, $$$b = 4$$$, $$$c = 9$$$
  • $$$a = 1$$$, $$$b = 4$$$, $$$c = 16$$$
  • $$$a = 1$$$, $$$b = 9$$$, $$$c = 16$$$
  • $$$a = 4$$$, $$$b = 9$$$, $$$c = 16$$$
  • $$$a = 2$$$, $$$b = 8$$$, $$$c = 18$$$