题目描述

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

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

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

输入格式

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

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

输出格式

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

3
3
6
9

0
1
1

数据范围

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