给定一个整数 $N$。请找出满足以下两个条件的正整数对 $(a, b)$ 的数量：

• $1 \le a, b \le N$
• 存在正整数 $(x, y)$ 使得 $x + y^2 = a$ 且 $x^2 + y = b$

给定 $T$ 组测试数据，请分别求解。

输入格式

输入通过标准输入按以下格式给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例 $case_i$ ($1 \le i \le T$) 的格式如下：

$N$

• 输入中的所有值均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 10^{18}$

输出格式

输出 $T$ 行。第 $i$ 行 ($1 \le i \le T$) 应包含第 $i$ 组测试数据的答案。

样例

输入 1

3
6
1
101

输出 1

4
0
83

说明

在第一个测试用例中，有四对 $(a, b)$ 满足条件：$(a, b) = (2, 2), (3, 5), (5, 3), (6, 6)$。 例如，对于 $(a, b) = (3, 5)$，选择 $(x, y) = (2, 1)$ 满足 $x + y^2 = 3 = a$ 且 $x^2 + y = 5 = b$，符合给定条件。