using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int[] products = new int[30001]; //we store repeated inputs here
        
        int t = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < t; a0++)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int product;
            if (products[n] == 0)
            {
                products[n] = -1;
                product = -1;
                for (int c = n/3; c <= n/2; c++)
                {
                    for (int b = 1; b < c; b++)
                    {
                        int a = n - c - b;
                        if (a <= b) //we want a <= b < c
                        {
                            if (a * a + b * b == c * c)
                            {
                                if (a * b * c > product)
                                {
                                    product = a * b * c;
                                    products[n] = product;
                                }
                            }
                        }
                    }
                }
            }
            Console.WriteLine(products[n]);

        }
    }
}