#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e7+10; int res[maxn],s[maxn*2]; bool vis[maxn*2]; void init(){ int n=2e7;vector<int>p;s[1]=1; up(i,2,2*n){ if(!vis[i])p.eb(i),s[i]=i; for(int x:p){ if(i*x>2*n)break; vis[i*x]=1;s[i*x]=(s[i]%x)?(s[i]*x):(s[i]/x); if(!(i%x))break; } } up(i,2,2*n)if(!(s[i]&(s[i]-1))){ ll val=sqrtl(i*1ll*s[i]); for(int j=0;j*j<=5*n/s[i];++j){ int a=i,b=s[i]*j*j; if((3*a+b)%8)continue; int y=(3*a+b)/8;if(y<=0||y>n)continue; int x=a-y;if(x<=0||x>n)continue; if(__gcd(x,y)!=1)continue; ll e=val*1ll*j; ll v1=-(y-x)-e,v2=-(y-x)+e; if(v1%2==0){ ll z=v1/2; if(z>=1&&z<=n)res[max({x,y,(int)z})]++; } if(v2%2==0&&v1!=v2){ ll z=v2/2; if(z>=1&&z<=n)res[max({x,y,(int)z})]++; } } } up(i,1,n)res[i]+=res[i-1]; } void slv(){ int n=read(); printf("%d\n",res[n]); } int main(){ //freopen("you.in","r",stdin),freopen("you.out","w",stdout); init();int t=read();while(t--)slv(); return 0; }