using System;
using System.Collections.Generic;

class Solution {
    static void Main(string[] args) {
        int n = 5 * (int)Math.Pow(10, 6);
        int[] answers = new int[n + 1];
        
        for (int t = 1; t < Math.Sqrt(n) + 1; t += 2) {
            for (int s = t + 2; s < Math.Sqrt(n) + 1; s += 2) {
                if (GCD(s, t) == 1) {
                    for (int i = s * (s + t); i <= n; i += s * (s + t)) {
                        answers[i]++;
                    }
                }
            }
        }

        int maxTri = 0;
        int answer = 0;
        List<int> finalAnswers = new List<int>();
        
        for (int i = 0; i <= n; i++) {
            int value = answers[i];
            if (value > maxTri) {
                answer = i;
                maxTri = value;
            }
            finalAnswers.Add(answer);
        }
        
        int q = int.Parse(Console.ReadLine());
        for (int i = 0; i < q; i++) {
            int inputN = int.Parse(Console.ReadLine());
            Console.WriteLine(finalAnswers[inputN]);
        }
    }
    
    static int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}