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

    // 找出 2 到 1000 之间的所有素数
    for(int i = 2; i <= 1000; i++) {
        if(is_pre(i)) {
            ob[cnt++] = i;
        }
    }
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        int l = 0, r = cnt - 1;
        // 二分查找第一个大于等于 a[i] 的素数的位置
        while(l < r) {
            int mid = (l + r) / 2;
            if(ob[mid] >= a[i]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 处理边界情况，如果 l 为 0，说明 a[i] 小于第一个素数
        if(l == 0) {
            cout << ob[l] << endl;
        } else {
            // 比较 ob[l] 和 ob[l - 1] 与 a[i] 的距离
            int diff1 = abs(ob[l] - a[i]);
            int diff2 = abs(ob[l - 1] - a[i]);
            if(diff1 < diff2 || diff1 == diff2) {
                cout << ob[l] << endl;
            } else {
                cout << ob[l - 1] << endl;
            }
        }
    }
    return 0;
}