#include <bits/stdc++.h>
using namespace std;

int main()
{
	
    int n;
    long long a[1000000 + 5];
    bool not_prime[1000000 + 5];
    vector <long long> prime;


    // sang nguyen to
    not_prime[1] = 1;
    int gh = 1e6;
    for(int i = 2; i * i <= gh; i ++)if(not_prime[i] == 0)
    for(int j = i * i; j <= gh;j += i)not_prime[j] = 1;
    for(int i = 1;i <= gh;i ++)if(not_prime[i] == 0)
    {
        long long so = 1LL * i * i;
        prime.push_back(so);
    }

    // nhap du lieu
    cin>>n;
    for(int i = 1; i <= n; i ++)cin>>a[i];

    //xu ly
    for(int i = 1; i <= n; i ++)
    {
        int it = lower_bound(prime.begin(),prime.end(),a[i]) - prime.begin();
        cout<<prime[it]<<' ';
    }

    return 0;
}