Волшебные тройки

Сложность: 33%

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

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

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

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

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

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

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

Подзадачи

№	баллы	необх. подзадачи	ограничения
1	10	-	$n ⩽ 100$
2	20	1	$n ⩽ 1 000$
3	30	1, 2	$n ⩽ 10 000$
4	40	1, 2, 3	Без дополнительных ограничений

STDIN	STDOUT
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$

Волшебные тройки

Войдите или зарегайтесь, чтобы сдать задачу

Попытка №