该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

数学课上会讲到，记直角三角形的三条边长度为 $a, b, c$ 且 $a \le b \le c$，那么有 $a^2 + b^2 = c^2$。

而有的三元组 $(a, b, c)$ 在满足 $a^2 + b^2 = c^2$ 的情况下也满足 $c = a^2 - b$，例如 $(3, 4, 5)$ 就是一个同时满足两个条件的三元组。

现在你需要求出同时满足这两个条件，且 $1 \le a \le b \le c \le n$ 的三元组有多少个。多组询问。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组数据一行一个整数 $n$。

输出格式

对于每组数据，输出一行一个整数，代表该组数据的答案。

数据范围

• 对于 $30\%$ 的数据，$n \le 100$；
• 对于 $60\%$ 的数据，$n \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^9$，$1 \le T \le 10^4$。

3
3
6
9

0
1
1