Imagine you have n
 light bulbs numbered 1,2,…,n
. Initially, all bulbs are on. To flip the state of a bulb means to turn it off if it used to be on, and to turn it on otherwise.

Next, you do the following:

for each i=1,2,…,n
, flip the state of all bulbs j
 such that j
 is divisible by i†
.
After performing all operations, there will be several bulbs that are still on. Your goal is to make this number exactly k
.

Find the smallest suitable n
 such that after performing the operations there will be exactly k
 bulbs on. We can show that an answer always exists.

†
 An integer x
 is divisible by y
 if there exists an integer z
 such that x=y⋅z
.

Input
Each test contains multiple test cases. The first line contains the number of test cases t
 (1≤t≤104
). The description of the test cases follows.

The only line of each test case contains a single integer k
 (1≤k≤1018
).

Output
For each test case, output n
 — the minimum number of bulbs.

Example
InputCopy
3
1
3
8
OutputCopy
2
5
11
Note
In the first test case, the minimum number of bulbs is 2
. Let's denote the state of all bulbs with an array, where 1
 corresponds to a turned on bulb, and 0
 corresponds to a turned off bulb. Initially, the array is [1,1]
.

After performing the operation with i=1
, the array becomes [0–,0–]
.
After performing the operation with i=2
, the array becomes [0,1–]
.
In the end, there are k=1
 bulbs on. We can also show that the answer cannot be less than 2
.

In the second test case, the minimum number of bulbs is 5
. Initially, the array is [1,1,1,1,1]
.

After performing the operation with i=1
, the array becomes [0–,0–,0–,0–,0–]
.
After performing the operation with i=2
, the array becomes [0,1–,0,1–,0]
.
After performing the operation with i=3
, the array becomes [0,1,1–,1,0]
.
After performing the operation with i=4
, the array becomes [0,1,1,0–,0]
.
After performing the operation with i=5
, the array becomes [0,1,1,0,1–]
.
In the end, there are k=3
 bulbs on. We can also show that the answer cannot be smaller than 5
.





this code passes all tests
#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (ll i = (a); i < (b); i++)
#define rloop(i, a, b) for (ll i = (b); i > (a); i--)
#define sz(x) ((ll)x.size())
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define upper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define pb push_back
#define mp make_pair
#define vi vector<ll>

typedef long long ll;
typedef long double ld;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll safeMult(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    if (a > INF / b) return INF;
    return a * b;
}

ll Pow(ll base, ll exp) {
    ll result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = safeMult(result, base);
            if (result == INF) return INF;
        }
        base = safeMult(base, base);
        if (base == INF) return INF;
        exp /= 2;
    }
    return result;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    
    ll n;
    cin >> n;
    
    ll l = n, h = n + sqrt(n) + 1;
    ll ans = -1;
    while (l <= h) {
        ll mid = l + (h -l)/2;
        ll x = mid - static_cast<ll>(sqrt(mid));
        
        if (x == n) {
            ans = mid;
            break;
        }
        else if (x < n) {
            l = mid + 1;
        }
        else {
            h = mid - 1;
        }
    }
    
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}


give me a better one than this