#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template <class c
#define mor > muu & operator<<(
#define ris return *this
#define eni(r) sim> typename enable_if <1 r sizeof(dud<c>(0)),muu&>::type operator<<(c g) {
sim> struct rge {c b,e ;};
sim> rge<c> range(c i, c j) {return rge<c>{i, j};}
sim> auto dud(c *r)-> decltype(cerr << *r);
sim> char dud(...);
struct muu {
	#ifdef LOCAL
	stringstream a;
	~muu() {cerr << a.str() << endl;}
	eni(<) a << boolalpha << g; ris;}
	eni(==) ris << range(begin(g), end(g));}
	sim, class m mor pair<m,c> r) {ris << "(" << r.first << ", " << r.second << ")";}
	sim mor rge<c> u) {
		a << "[";
		for (c i = u.b; i != u.e; ++i)
			*this << ", " + 2 * (i == u.b) << *i;
		ris << "]";
	}
	#else
	sim mor const c&) {ris;}
	#endif
	muu & operator()(){ris;}
};
#define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")
#define imie(r) "[" #r ": " << (r) << "] "
#define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
#define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
#define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] "

using ll=long long;
const int nax=1000*1007;

ll dp[nax];

ll jed[nax];
ll dwa[nax];
ll trz[nax];

void test()
{
	int n;
	scanf("%d", &n);
	debug() << jed[n] << " " << dwa[n] << " " << trz[n];
	printf("%lld\n", (jed[n]-dwa[n]*3+2*trz[n])/6);
}

int main()
{
	dp[1]=1;
	for (int h=1; h<=3; h++)
		for (int i=nax-1; i; i--)
			for (int j=2*i; j<nax; j+=i)
				dp[j]+=dp[i];
	for (int i=1; i<nax; i++)
		jed[i]=dp[i];
	memset(dp, 0, sizeof(dp));
	for (int i=1; i*i<nax; i++)
		dp[i*i]=1;
	for (int i=nax-1; i; i--)
		for (int j=2*i; j<nax; j+=i)
			dp[j]+=dp[i];
	for (int i=1; i<nax; i++)
		dwa[i]=dp[i];
	memset(dp, 0, sizeof(dp));
	for (int i=1; i*i*i<nax; i++)
		trz[i*i*i]=1;
	for (int i=1; i<nax; i++)
	{
		jed[i]+=jed[i-1];
		dwa[i]+=dwa[i-1];
		trz[i]+=trz[i-1];
	}
	
	int t;
	scanf("%d", &t);
	while(t--)
		test();
	return 0;
}