CF2020B.Brightness Begins

想象你有 $n$ 个编号为 $1, 2, \ldots, n$ 的灯泡。最初，所有灯泡都是开着的。翻转一个灯泡的状态意味着如果它原来是开着的，就把它关掉；否则就把它打开。

接下来，您需要执行以下操作：

对于每个 $i=1,2,\ldots,n$，翻转所有灯泡 $j$ 的状态，使得 $j$ 能被 $i^\dagger$ 整除。

在执行完所有操作后，将会有一些灯泡仍然亮着。你的目标是使这个数量恰好为 $k$。

找到最小的合适 $n$，使得执行操作后，灯泡的数量恰好为 $k$。我们可以证明答案总是存在的。

$ ^\dagger $ 如果存在一个整数 $ z $ 使得 $ x = y\cdot z $ ，那么一个整数 $ x $ 可以被 $ y $ 整除。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1\le t\le 10^4$）。测试用例的描述如下。

每个测试用例的唯一一行包含一个整数 $k$（$1\le k\le 10^{18}$）。

对于每个测试用例，输出 $n$——最小灯泡数量。

在第一个测试用例中，最小数量的灯泡是 $2$。让我们用一个数组来表示所有灯泡的状态，其中$1$对应于打开的灯泡，$0$ 对应于关闭的灯泡。最初，数组是 $[1, 1]$。

• 在执行了 $i=1$ 的操作后，数组变成了 $[\underline{0},\underline{0}]$。
• 在执行了 $i=2$ 的操作后，数组变成了 $[0,\underline{1}]$。

最后，有 $k=1$ 个灯泡亮着。我们还可以证明答案不可能小于 $2$。

在第二个测试用例中，最小数量的灯泡是 $5$。最初，数组是 $[1, 1, 1, 1, 1]$。

• 在执行了 $i=1$ 的操作后，数组变成了 $[\underline{0},\underline{0},\underline{0},\underline{0},\underline{0}]$。
• 在执行了 $i=2$ 的操作后，数组变成了 $[0,\underline{1},0,\underline{1},0]$。
• 在执行了 $i=3$ 的操作后，数组变成了 $[0,1,\underline{1},1,0]$。
• 在执行了 $i=4$ 的操作后，数组变成了 $[0,1,1,\underline{0},0]$。
• 在执行了 $i=5$ 的操作后，数组变成了 $[0,1,1,0,\underline{1}]$。

最后，有 $k=3$ 个灯泡亮着。我们还可以证明答案不可能小于 $5$。

翻译者：jiangyunuo。