Problem: codeforces/2020B
Time limit: 1000 ms, Memory limit: 256 MB

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.


Sample Input 1

```
3
1
3
8
```

Sample Output 1

```
2
5
11
```

Notes

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