#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=3000;
int main()
{
	vector<long long > ans(N+100,-1);
	for(int i=1;i<=N;++i)
		for(int j=1;j<=N;++j)
		{
			int c=i*i+j*j;
			double sq=sqrt( static_cast<double>(c));
			if(ceil(sq)==static_cast<int>(sq) )
			{
				int k=static_cast<int>(sq);
				if(i+j+k<=N)
					ans[i+j+k]=max(ans[i+j+k],static_cast<long long>(i*j*k));
			}
		}
	int t;
	cin>>t;
	for(int k=1;k<=t;++k)
	{
		int n;
		cin>>n;
		cout<<ans[n]<<endl;
	}
}