#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[10000005];
int sum[10000005];
vector<int> prime;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	for(int i=2;i<=10000000;i++){
		if(vis[i]==0){
			for(int j=2;j<=10000000/i;j++)vis[min(i*j,10000000ll)]=1;
			prime.push_back(i);
		}
	}
	for(int x=1;x*x*x*x<=10000000;x++)
		for(int y=1;y*y<=10000000;y++)
			if(vis[min(x*x*x*x+y*y,10000000ll)]==0)
				sum[min(x*x*x*x+y*y,10000000ll)]=1;
	for(int i=1;i<=10000000;i++)sum[i]+=sum[i-1];
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		cout<<sum[n]<<"\n";
	}
	return 0;
}