B. Да будет свет!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ лампочек, пронумерованных числами $$$1, 2, \ldots, n$$$. Изначально все лампочки включены. Под инвертированием состояния лампочки подразумевается её выключение, если она была включена, и её включение, иначе.

Затем вы делаете следующее:

  • для каждого $$$i = 1, 2, \ldots, n$$$, инвертировать состояние всех лампочек $$$j$$$, таких что $$$j$$$ делится на $$$i^\dagger$$$.

После выполнения всех операций некоторые лампочки по-прежнему будут включены. Ваша цель — сделать так, чтобы число таких лампочек было ровно $$$k$$$.

Найдите наименьшее подходящее $$$n$$$, такое что после выполнения всех операций включены будут ровно $$$k$$$ лампочек. Можно показать, что ответ всегда существует.

$$$^\dagger$$$ Целое число $$$x$$$ делится на $$$y$$$, если существует целое $$$z$$$, такое что $$$x = y\cdot z$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^{18}$$$).

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ — наименьшее число лампочек.

Пример
Входные данные
3
1
3
8
Выходные данные
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$$$.