#include <bits/stdc++.h>

#define rep(i,a,n) for(int i = a; i < (n); ++i)

typedef long long ll;

using namespace std;

const int MAX_PR = 1000003;
bitset<MAX_PR> isprime;
vector<vector<pair<int, int>>> fact(MAX_PR);
unordered_map<string, int> mem;

vector<int> a(20);
vector<int> b(20);
vector<int> c(20);
vector<int> cntt(MAX_PR);
string g;

void bt(int n, int p, vector<int>& expy) {
	int exp = expy[p];
	//cout << n << " " << p << endl;
	rep(i,0,exp+1) {
		rep(j, i, exp+1) {
			int k = exp - j;
			a[p] = i;
			b[p] = j-i;
			c[p] = k;
			if (p+1 < expy.size()) {
				bt(n, p+1, expy);
			}
			else {
				bool ok1 = false;
				bool ok2 = false;
				bool ok3 = false;
				for (int ind = 0; ind < p+1; ind++) {
					if (a[ind] != b[ind]){
						ok1 = true;
					}
					if(a[ind] != c[ind]){
						ok2 = true;
					}
					if(b[ind] != c[ind]){
						ok3 = true;
					}
				}
				if (ok1 && ok2 && ok3){
					cntt[n] += 1;
				}

			}

		}
	}
}
vector<int> eratosthenes_sieve(int lim) {
	isprime.set(); isprime[0] = isprime[1] = 0;
	for(int i = 4; i < lim; i+=2) isprime[i] = 0;
	for(int i = 3; i*i < lim; i+= 2) if (isprime[i])
		for(int j = i*i; j < lim; j += i*2) isprime[j] = 0;
	vector<int> pr;
	rep(i,2,lim) if (isprime[i]) pr.push_back(i);
	return pr;
}
int main() {
	vector<int> pr = eratosthenes_sieve(MAX_PR);

	for(auto p : pr) {
		int tmp = p;
		fact[tmp].push_back({p,1});
		//cout << "PUSH OK" << endl;
		while (tmp+p < MAX_PR) {
			tmp += p;
			int d = tmp/p;
			if(fact[d].size() > 0 && fact[d].back().first == p)
				fact[tmp].push_back({p,fact[d].back().second + 1});
			else
				fact[tmp].push_back({p,1});
		}
	}

	//cout << "SPOCTENO" << endl;

	/*for (int i = 0; i < fact.size(); i++) {
		auto num = fact[i];
		cout << i << endl;
		for (auto pr : num )
			cout << pr.first << " " << pr.second << endl;
	}*/
	
	for (int i = 2; i < MAX_PR; i++) {
		vector<int> expy;
		for(auto par : fact[i]){
			expy.push_back(par.second);
			//if (i < 20) cout << par.first << " " << par.second << endl;
		}
		//cout << "EXPENO" << " " << expy.size() << endl;
		sort(expy.rbegin(), expy.rend());
		//cout << "SORTENO" << endl;
		g = "";
		for(int exp : expy) {
			g += 'a' + exp;
		}
		//cout << "stringnadtrs" << endl;
		if(mem.count(g) == 0) {
			//cout << "v fu" << endl;
			bt(i,0, expy);
			cntt[i] /= 6;
			mem[g] = cntt[i];
		}
		else{
			//cout << "else" << endl;
			cntt[i] = mem[g];
		}
	}
	//cout << "arstaoirsterst" << endl;
	vector<int> pfsum(MAX_PR);
	pfsum[1] = 0;
	for (int i = 2; i < MAX_PR; i++){
		pfsum[i] = pfsum[i-1] + cntt[i];
	}

	int pocet;

	cin >> pocet;
	rep(i, 0, pocet){
		int cislo;
		cin >> cislo;
		cout << pfsum[cislo] << endl;
	}
	return 0;
}