#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define rpt(i,l,r) for(int i=l;i<=r;i++)
#define rpd(i,r,l) for(int i=r;i>=l;i--)
int tag[35001],pr[9999],tot;
int T;
long long x;
int check(int x){
    if(x<=1) return 0;
    int t=1;
    while(x>1){
        int s=0;
        while(x%pr[t]==0) x/=pr[t],s++;
        if(s>1) return 0;
        t++;
        if(t>tot) break;
    }
    return 1;
}
int main(){
    rpt(i,2,35000) tag[i]=0;
    tot=0;
    rpt(i,2,35000) if(!tag[i]){
        pr[++tot]=i;
        rpt(j,2,35000/i) tag[i*j]=1;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%I64d",&x);
        int upmn,dnmx;
        dnmx=int(sqrt(x));
        upmn=dnmx+1;
        while(!check(upmn)) upmn++;
        while(!check(dnmx)){
            dnmx--;
            if(dnmx<=1){
                dnmx=-233;
                break;
            }
        }
        if(dnmx==-233) printf("%I64d\n",1LL*upmn*upmn-x);
        else if(1LL*upmn*upmn-x<x-1LL*dnmx*dnmx) printf("%I64d\n",1LL*upmn*upmn-x);
        else printf("%I64d\n",x-1LL*dnmx*dnmx);
    }
}