H. Последнее число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано мультимножество $$$S$$$. Изначально $$$S = \{1,2,3, \ldots, n\}$$$.

Вы выполните следующую операцию $$$n-1$$$ раз.

  • Выберите наибольшее число $$$S_{\text{max}}$$$ в $$$S$$$ и наименьшее число $$$S_{\text{min}}$$$ в $$$S$$$. Удалите эти два числа из $$$S$$$ и добавьте $$$S_{\text{max}} - S_{\text{min}}$$$ в $$$S$$$.

Легко показать, что после $$$n-1$$$ операций останется ровно одно число. Выведите это число.

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

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

Для каждого набора входных данных в одной строке содержится целое число $$$n$$$ ($$$2 \le n \le 10^9$$$) — изначальный размер множества $$$S$$$.

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

Для каждого набора входных данных выведите число, которое останется после $$$n-1$$$ операции.

Пример
Входные данные
5
2
4
7
15
177567
Выходные данные
1
2
2
4
33914
Примечание

Покажем, как изменится мультимножество $$$S$$$ при $$$n=4$$$.

  • Операция $$$1$$$: $$$S=\{1,2,3,4\}$$$, удаляем $$$4$$$ и $$$1$$$, добавляем $$$3$$$.
  • Операция $$$2$$$: $$$S=\{2,3,3\}$$$, удаляем $$$3$$$ и $$$2$$$, добавляем $$$1$$$.
  • Операция $$$3$$$: $$$S=\{1,3\}$$$, удаляем $$$3$$$ и $$$1$$$, добавляем $$$2$$$.
  • Получившееся мультимножество: $$$S = \{2\}$$$.

Таким образом, при $$$n = 4$$$ ответ равен $$$2$$$.