Brightness Begins
Contest: Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
Difficulty rating: 1200
Tags: binary search, math

Imagine you have $$$n$$$ light bulbs numbered $$$1, 2, \ldots, 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, \ldots, n$$$, flip the state of all bulbs $$$j$$$ such that $$$j$$$ is divisible by $$$i^\dagger$$$.

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.

$$$^\dagger$$$ An integer $$$x$$$ is divisible by $$$y$$$ if there exists an integer $$$z$$$ such that $$$x = y\cdot z$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$k$$$ ($$$1 \le k \le 10^{18}$$$).

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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 $$$[\underline{0}, \underline{0}]$$$.
- After performing the operation with $$$i = 2$$$, the array becomes $$$[0, \underline{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 $$$[\underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{0}]$$$.
- After performing the operation with $$$i = 2$$$, the array becomes $$$[0, \underline{1}, 0, \underline{1}, 0]$$$.
- After performing the operation with $$$i = 3$$$, the array becomes $$$[0, 1, \underline{1}, 1, 0]$$$.
- After performing the operation with $$$i = 4$$$, the array becomes $$$[0, 1, 1, \underline{0}, 0]$$$.
- After performing the operation with $$$i = 5$$$, the array becomes $$$[0, 1, 1, 0, \underline{1}]$$$.

In the end, there are $$$k = 3$$$ bulbs on. We can also show that the answer cannot be smaller than $$$5$$$.

Example input:
3
1
3
8

Example output:
2
5
11

Editorial:
For any bulb $$$i$$$, its final state depends on the parity of the number of divisors of $$$i$$$. If $$$i$$$ has an even number of divisors, then bulb $$$i$$$ will be on; else it will be off. This translates to, if $$$i$$$ is not a perfect square, bulb $$$i$$$ will be on; else it will be off. So now the problem is to find the $$$k$$$th number which is not a perfect square. This can be done by binary searching the value of $$$n$$$ such that $$$n- \lfloor \sqrt{n} \rfloor = k$$$ or the direct formula $$$n$$$ = $$$\lfloor k + \sqrt{k} + 0.5 \rfloor$$$.