[R57E]MyName - 代码源竞赛平台

时空限制

1s/512M

题目描述

我的名字

从你的前前前世开始 我就一直寻觅着你的踪迹

jiangly 想要寻觅名字。

所谓名字，其实就是一个有序三元组 $(x,y,z)$，满足 $1\le x,y,z \le n$。

jiangly 想要一个特殊的名字。

所以，他希望有 $x^2-y^2=z^3$ 这个优美的性质。

现在 jiangly 已经算出了有多少种满足这个性质的名字，他想考考你满足条件的三元组的数量。

格式

输入格式

本题采用多测。

输入的第一行包含一个整数 $T$，表示测试组数。

接下来 $T$ 行，每行一个正整数 $n$，含义如题所述。

输出格式

对于每组测试，输出满足条件的三元组的数量。

样例

样例输入 #1

3
3
10
1000000

样例输出 #1

1
3
82319

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分值	$T\le$	$n \le$
$1$	$20$	$10$	$1000$
$2$	$20$		$10^5$
$3$	$60$	$10^5$	$10^6$

对于 $100\%$ 的数据，$1\le T\le 10^5,1\le n \le 10^6$。