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

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    string s;

    while (cin >> n) {
        while (n--) {
            cin >> s;

            // 提取所有数字
            string numStr = "";
            for (char c : s) {
                if (isdigit(c)) numStr += c;
            }

            if (numStr.empty()) {
                cout << 0 << endl;
                continue;
            }

            int a = stoi(numStr);

            // 从a往下找素数
            for (int i = a; i >= 2; i--) {
                if (isPrime(i)&&a%i==0) {
                    cout << i << endl;
                    break;
                }
            }
        }
    }
    return 0;
}