package com.company;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int size = s.nextInt();
        for (int i = 0; i < size; i++) {
            System.out.print(lampa(s.nextInt()) + " ");
        }
    }

    public static int lampa(int a) {
        int razm = 2000000;
        int prost[]=new int[10000000];
        boolean mas[] = new boolean[10000000];
        for(int i=1;i<=Math.sqrt(razm);i++) {

            for(int j=1;j<=Math.sqrt(razm);j++) {

                int k = 0, f1 = 4 * i * i + j * j, f2 = 3 * i * i + j * j, f3 = 3 * i * i - j * j;
                if (((f1) % 12 == 1) || ((f1) % 12 == 5)) {
                    k++;
                    mas[f1] = true;
                }
                if ((f2) % 12 == 7) {
                    k++;
                    mas[f2] = true;
                }
                if ((i > j) && (f3) % 12 == 11) {
                    k++;
                    mas[f3] = true;
                }
                if (k > 1) {
                    if (f1 == f2) mas[f1] = false;
                    else if (f1 == f3) mas[f1] = false;
                    else if (f2 == f3) mas[f2] = false;

                }

            }

        }
        for (int i=1;i<=razm;i++)
        for (int j=5;j<=Math.sqrt(razm);j++)
            if(mas[i]==true&&mas[j]==true&&(i%(j*j)==0))
                mas[i]=false;
        int j=3;
for (int i=0;i<razm+3100;i++)
    if(mas[i]==true) {
        prost[j] = i;
        j++;
    }
prost[1]=2;
        prost[2]=3;
        //a) 4*x^2+y^2;
        //b) 3*x^2+y^2;
        //c) 3*x^2-y^2, значение вычисляется только при x>y.
return prost[a];
    }
}