# Enter your code here. Read input from STDIN. Print output to STDOUT
import math
from collections import defaultdict

n, pyth, minval = 5*10**6, defaultdict(int), 0

for i in range(1, int(math.sqrt(n))):
    for j in range(1, i):
        if math.gcd(i, j) == 1:
            a, b, c = i**2-j**2, 2*i*j, i**2+j**2 #Eulers formula
            if not math.gcd(a, b, c) == 1: #filter non primitive triplets to avoid duplication
                continue
            if a+b+c > n:
                break
            k = 1
            while True:
                pyth[k*(a+b+c)] += 1
                k += 1
                if k*(a+b+c) > n:
                    break
vals = [(0,0)]
for i in sorted(pyth):
    if pyth[i] > vals[-1][1]:
        vals.append((i, pyth[i]))
        
def search(v, l, r, a):
    if l == r:
        if v < a[l][0]:
            return(a[l-1][0])
        return(a[l][0])
    m = (l+r)//2
    if v <= a[m][0]:
        return(search(v, l, m, a))
    else:
        return(search(v, m+1, r, a))
       
for a0 in range(int(input())):
    N = int(input())
    print(search(N, 0, len(vals)-1, vals))

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        int n = 5 * (int)Math.pow(10, 6);
        int[] answers = new int[n + 1];

        for (int t = 1; t * t <= n; t += 2) {
            for (int s = t + 2; s * s <= n; 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<Integer> finalAnswers = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            int value = answers[i];
            if (value > maxTri) {
                answer = i;
                maxTri = value;
            }
            finalAnswers.add(answer);
        }

        Scanner scanner = new Scanner(System.in);
        int q = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < q; i++) {
            n = Integer.parseInt(scanner.nextLine());
            System.out.println(finalAnswers.get(n));
        }
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

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;
    }
}

import itertools, math
n=5*10**6
answers=[0]*(n+1)
for item in itertools.combinations(range(1,int(n**0.5)+1,2),r=2): #implementing euclid's theorem, where sides are (s^2-t^2)/2, st, (s^2+t^2)/2 and s>t, s and t are odd coprime numbers. 
    t=item[0]
    s=item[1]
    if math.gcd(s,t) == 1:
        for i in range(s*(s+t),n+1,s*(s+t)): #I don't have to worry about repeats like for any different s and t if I will get the same sides, cause for one triplet of sides only one primitive triplet will exist and they won't repeat and I can always add 1 in the line below.
            answers[i]+=1

max_tri=0
answer=0
final_answers=[] #our answers
for i in range(0,n+1):
    value=answers[i]
    if value>max_tri:
        answer=i
        max_tri=value
    final_answers.append(answer)
    
    
for _ in range(int(input())):
    n=int(input())
    print(final_answers[n])