题意描述

小水母看到了一个方程！

她有三个整数变量 $x,y,z \in [1,n]$ 以及一个方程 $x^2-xy-y^2+yz+z^2-zx=0$ ，她想知道这个方程有多少解。

但是这个问题还是太简单了，她想知道这个方程有多少个满足 $\gcd(x,y,z) = 1$的解。

她有 $T$ 次询问，如果你能正确回答这些询问，她会奖励你一百分！

输入格式

一行一个正整数 $T$。

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

输出格式

$T$ 行每行一个非负整数，表示答案。

样例

样例输入 #1:

5
6
8
21
53
74

样例输出 #1:

2
3
7
15
23

样例 #2 见下发文件。

数据范围

对于所有测试点，$1 \le T \le 5000,1 \le n \le 2 \times 10^7$。