#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main()
{
    int q; cin >> q;
    unordered_map<ll, pair<int, vector<int>>> mp;
    for(int i = 0; i < q; ++i) {
        int n;
        cin >> n;
        if(mp.find(n) != mp.end()) {
		mp[n].second.push_back(i);
	} else {
		mp[n] = {n+1, {i}};
	}
        if(n == 1) mp[n].first = 1;
    }
    for(int i = 1; i < 100000; ++i) {
	ll v = 1;
    	for(int j = 1; j < i; ++j) {
            // cerr << v << ' ';
            v *= i - j;
            v /= j;
            if(v > 2e9) break;
            if(mp.find(v) == mp.end()) continue;
            mp[v].first = min(mp[v].first, i);
        }
        // cerr << '\n';
    }

    vector<int> oo(q);
    for(auto a : mp) {
	for(auto b : a.second.second) {
            oo[b] = a.second.first;
	}
    }

    for(auto a : oo) {
    	cout << a << '\n';
    }

    return 0;
}