A. Время пиццы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хао и Алекс — хорошие друзья. После того как они вместе выиграли соревнование по программированию, они получили огромную пиццу в качестве приза.

Изначально им даётся $$$n$$$ кусочков пиццы. Каждый день происходит следующий процесс:

  • Если осталось не более $$$2$$$ кусочков, Алекс съедает их все.
  • В противном случае, пусть $$$m$$$ — текущее количество кусочков ($$$m\ge 3$$$). Хао делит их на три группы размерами $$$m_1$$$, $$$m_2$$$ и $$$m_3$$$ так, что:

    $$$$$$m_1 + m_2 + m_3 = m\text{ и } 1 \le m_1\le m_2\le m_3.$$$$$$

    Затем:

    • Хао съедает $$$m_1$$$ кусочков (самую маленькую группу).
    • Алекс съедает $$$m_2$$$ кусочков (среднюю группу).
    • Оставшиеся $$$m_3$$$ кусочков (самая большая группа) переносятся на следующий день.

Ваша задача — определить максимальное общее количество кусочков, которое Хао может съесть, если он всегда выбирает разбиение оптимально.

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

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

Первая и единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^9$$$) — начальное количество кусочков пиццы.

Обратите внимание, что нет дополнительного ограничения на сумму $$$n$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите одно целое число — максимальное количество кусочков, которое Хао может съесть суммарно.

Пример
Входные данные
3
8
4
3
Выходные данные
3
1
1
Примечание

В первом наборе входных данных Хао может съесть $$$3$$$ кусочка следующим образом:

  1. Разделить на $$$m_1 = 2$$$, $$$m_2 = 3$$$ и $$$m_3 = 3$$$. Хао съедает $$$2$$$ кусочка, Алекс съедает $$$3$$$ кусочка, и оставшиеся $$$3$$$ кусочка переносятся на следующий день.
  2. Разделить на $$$m_1 = 1$$$, $$$m_2 = 1$$$ и $$$m_3 = 1$$$. Хао съедает $$$1$$$ кусочек, Алекс съедает $$$1$$$ кусочек, и оставшийся $$$1$$$ кусочек переносится на следующий день.
  3. Остался только $$$1$$$ кусочек, поэтому Алекс съедает его.

Во втором наборе входных данных Хао может съесть $$$1$$$ кусочек следующим образом:

  1. Разделить на $$$m_1 = 1$$$, $$$m_2 = 1$$$ и $$$m_3 = 2$$$. Хао съедает $$$1$$$ кусочек, Алекс съедает $$$1$$$ кусочек, и оставшиеся $$$2$$$ кусочка переносятся на следующий день.
  2. Осталось только $$$2$$$ кусочка, поэтому Алекс съедает их все.