D. Катет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано одно целое число $$$x$$$. Найдите количество различныx прямоугольных треугольников ненулевой площади с целыми сторонами, что один из катетов равен $$$x$$$. Два треугольника считаются различными, если их нельзя наложить друг на друга при помощи параллельных сдвигов, поворотов и отражений.

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

В первой строке дано одно целое число $$$t$$$ $$$(1 \le t \le 5)$$$ — количество наборов входных данных.

В каждой из последующих $$$t$$$ строк дано одно целое число $$$x$$$ $$$(1 \le x \le 10^9)$$$ — длина катета.

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

Выведите $$$t$$$ строк — количество прямоугольных треугольников с катетом $$$x$$$ для каждого набора входных данных.

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

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

ГруппаБаллыДополнительные ограниченияНеобходимые группыКомментарий
00——Тесты из условия
130$$$x \le 40$$$0Можно доказать, что при $$$x \le 40$$$, длины всех сторон всех подходящих треугольников не превышают $$$1000$$$.
225$$$x \le 1000$$$0, 1
315$$$x \le 10^5$$$0, 1, 2
410$$$x = 2^k$$$, $$$1 \le k \le 29$$$—
520$$$x \le 10^9$$$0-4
Пример
Входные данные
2
15
2
Выходные данные
4
0
Примечание

Для $$$x=15$$$ существует ровно $$$4$$$ различных прямоугольных треугольника с целочисленными сторонами: $$$(8, 15, 17)$$$, $$$(15, 20, 25)$$$, $$$(15, 36, 39)$$$ и $$$(15, 112, 113)$$$.