今天是 Carrie 在 Blaniel 高中的第一天。

在她的第一节数学课上，老师 Jeffery 先生给她讲了一个关于小高斯（Gauss）的著名故事。

当小高斯还在上小学时，他的老师为了能稍微休息一下，让全班同学把从 1 到 100 的所有数字加起来。然而，令老师惊讶的是，高斯很快就发现了将数字两两配对相加的技巧，并写下了答案 $101 \times 50 = 5050$。

可能是因为讲完这个故事后感到疲倦，Jeffery 先生要求全班同学计算给定整数 $N$ 下的勾股数（Pythagorean triples）数量。

如果三个正整数 $a, b, c$ 满足 $a^2 + b^2 = c^2$，则称三元组 $(a, b, c)$ 为勾股数。

Carrie 需要计算满足 $c \le N$ 的不同勾股数的数量。请注意，由于 $a$ 和 $b$ 的对称性，勾股数 $(a, b, c)$ 和 $(b, a, c)$ 应视为同一个。

Carrie 的数学天赋不如高斯，但她知道她的男朋友可能很擅长数学。现在作为 Carrie 的男朋友，你能帮她解决 Jeffery 先生的问题吗？

输入格式

输入的第一行是一个整数 $T$ ($T \le 10$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含一个整数 $N$ ($1 \le N \le 10^9$)，表示你需要计算满足 $c \le N$ 的三元组 $(a, b, c)$ 的数量。

输出格式

对于每个测试用例，输出一行答案。

样例

输入 1

2
5
20

输出 1

1
6

说明 1

所有小于等于 20 的勾股数为： $(3,4,5), (5,12,13), (6,8,10), (8,15,17), (9,12,15), (12,16,20)$