B. Brightness Begins
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\).
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}\)).
For each test case, output \(n\) — the minimum number of bulbs.
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\).