Областная олимпиада по информатике. 9 класс. 2014-2015 учебный год.

Задача E. Треугольники

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Посчитайте количество различных треугольников с целыми сторонами, имеющих площадь равную $\sqrt S.$ Формула Герона для площади треугольника: $\sqrt{p(p-a)(p-b)(p-c)},$ где $p = (a+b+c)/2,$ $a,$ $b,$ $c$ — длины сторон треугольника.

Формат входного файла

В первой строке входных данных задано целое число $1 \le T \le 4$ — количество тестов. В следующих $T$ строках заданы по одному целому числу $1 \le S \le 10^{18}.$

Формат выходного файла

Выведите $T$ — строк, в каждой строке ответ на соответствующий тест.

Примеры:

Вход

3
8
13
60

Ответ

1
0
0

Замечание

$S \le 100 $— $10\%$ тестов;
$S \le 1000 $— $20\%$ тестов;
$S \le 10^6 $— $30\%$ тестов;
$S \le 10^9 $— $40\%$ тестов;
$S \le 10^{12} $— $50\%$ тестов.