#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 20000;
typedef long long int ll;
int a[MAXN], cnt = 0;
void init() {
    for(int i = 2; i <= MAXN; i++) {
        int flag = 1;
        for(int j = 2; j*j <=i; j++) {
            if(i%j == 0) {
                flag = 0;
                break;
            }
        }
        if(flag) {
            a[cnt++] = i;
        }
    }
}
int main() {
    int t;
    ios::sync_with_stdio(false);
    cin >> t;
    init();
    while(t--) {
        ll n, x1 = -1, x2 = -1;
        cin >> n;
        ll m = sqrt(n);
        for(int i = m+1;; i++) {
            int res = i, flag = 1;
            for(int j = 0; j < cnt; j++) {
                int num = 0;
                while(res % a[j] == 0) {
                    res /=a[j];
                    num++;
                    if(num > 1) {
                        flag = 0;
                        break;
                    }
                }
                if(flag == 0 || res == 1) break;
            }
            if(flag == 1) {
                x1 = i;
                break;
            }
        }
        for(int i = m; i >= 2; i--) {
            int res = i, flag = 1;
            for(int j = 0; j < cnt; j++) {
                int num = 0;
                while(res % a[j] == 0) {
                    res /=a[j];
                    num++;
                    if(num > 1) {
                        flag = 0;
                        break;
                    }
                }
                if(flag == 0 || res == 1) break;
            }
            if(flag == 1) {
                x2 = i;
                break;
            }
        }
        // cout << x1 <<" "<< x2 <<" "<<m <<endl;

        if(x1== -1) {
            x2 = x2*x2;
            cout<< abs(x2-n) << endl;
        } else if(x2 == -1) {
            x1 = x1*x1;
            cout << abs(x1-n)<< endl;
        } else {
            x1 = x1*x1;
            x2 = x2*x2;
            cout <<min(abs(x1 - n), abs(x2- n)) << endl;
        }


    }
    return 0;
}