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])