← 返回题目列表

Codeforces · 2020/B

B. 亮度开始

中文机器翻译题面 查看原题

想象一下,您有 $$$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$$$ — 灯泡的最小数量。

示例

输入 #1

3
1
3
8

输出 #1

2
5
11

注意

在第一个测试用例中,灯泡的最小数量为 $$$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$$$。