CF2020B Brightness Begins

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 $ .