#include <bits/stdc++.h>
#define N 1000010
using namespace std;

int arr[N];
vector< vector< int>> fact(N);

set<long long> mp;

long long int results[N];
int flags[N];


void sieve()
{
	for(int i=2; i<N; i++)
	{
		if(arr[i] == 0)
		{
			int j = 1;
			while(i*j < N)
			{
				arr[i*j]++;
				fact[i*j].push_back(i);
				j++;
			}
		}else{
			if(arr[i] == 1)
			{
				int p = fact[i][0];
				for(int j=i; j<N; j+=i)
				{
					fact[j].push_back(p);
				}
			}
		}
	}
}

int in_map(int a, int b, int c)
{
	int x = min(a, min(b, c));
	int y = max(a, max(b, c));
	int z = a + b +c - x - y;
	long long key = x*N*N + y * N + z;
	
	if(mp.find(key) == mp.end())
	{
		mp.insert(key);
		return 0;
	}
	
	return 1;
	
} 
long long int rec(int a, int b, int c, int idx, int len, int i)
{
	if(in_map(a, b, c))
		return 0;
	
	if(idx == len){
		if(a!=b && a!=c && b!=c)
			return 1;
			
		return 0;
	}
	
	return rec(a*fact[i][idx], b, c, idx+1, len, i) + 
			rec(a, b*fact[i][idx], c, idx+1, len, i) +
			rec(a, b, c*fact[i][idx], idx+1, len, i);
}

long long int cnt(int i)
{
	return rec(1,1,1,0,fact[i].size(), i);
}

void update(int curmax, int max)
{
	for(int i=curmax+1; i<=max; i++)
	{
		mp = set<long long>();
		results[i] = results[i-1];
		results[i] += cnt(i);
	}
}		
int main()
{
	results[0] = 0;

	sieve();
	int curmax =0
	for(int i=1; i<N; i++)
	{
		mp = set<long long>();
		results[i] = results[i-1];
		results[i] += cnt(i);
	}
	
	int a, b;
	cin >> a;
	while(a--)
	{
		scanf("%d", &b);
		if(b > curmax)
		{
			update(curmax, b);
			curmax = b;
		}
		printf("%llu\n", results[b]);
	}
	return 0;
}