给一个正整数n，其中n<=$10^7$，求使得gcd(x,y)为质数的(x,y)的个数，1<=x,y<=n。
输入：
第一行一个数T 表示有T组数据
接下来T行，每行一个数n
输出：
n 行，每行一个数，表示答案

样例：
输入：
3
10
100
1000
输出：
30
2791
275034