Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×
A. Рабочая неделя
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваша рабочая неделя состоит из $$$n$$$ дней, пронумерованных от $$$1$$$ до $$$n$$$, после дня $$$n$$$ снова идет день $$$1$$$. И $$$3$$$ из этих дней — выходные, одним из которых является последний день, день $$$n$$$. Когда будут два остальных дня — вам предстоит выбрать.

Выбирая дни отдыха, вы преследуете две цели:

  • Никакие два выходных дня не должны идти друг за другом. Обратите внимание, что вы не можете сделать день $$$1$$$ выходным, потому что он следует за днем $$$n$$$.
  • Рабочие отрезки, оказавшиеся между выходными должны быть наименее похожи друг на друга. Более конкретно, если отрезки имеют длину $$$l_1$$$, $$$l_2$$$ и $$$l_3$$$ дней, вы хотите максимизировать $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$.

Выведите максимальное значение выражения $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$, которое может быть получено.

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Описание наборов входных данных следует ниже.

Единственная строка каждого набора содержит одно целое число $$$n$$$ ($$$6 \le n \le 10^9$$$).

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

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

Пример
Входные данные
3
6
10
1033
Выходные данные
0
1
342
Примечание

На изображении ниже можно видеть решения из примера для первых двух наборов данных. Выбранные выходные изображены фиолетовым. Рабочие отрезки подчеркнуты зеленым.

В $$$1$$$ наборе данных единственными вариантами для выходных являются дни $$$2$$$, $$$3$$$ и $$$4$$$ (потому что дни $$$1$$$ и $$$5$$$ соседние с днем $$$n$$$). Поэтому единственная возможность расположить их, чтобы они не стали соседями — это выбрать дни $$$2$$$ и $$$4$$$. Таким образом $$$l_1 = l_2 = l_3 = 1$$$, а ответ $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0$$$.

Для $$$2$$$ набора данных изображен один из способов выбора выходных. Рабочие отрезки имеют длины $$$2$$$, $$$1$$$ и $$$4$$$ дней. Таким образом, минимальной разницей является $$$1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|)$$$. Можно показать, что нет возможности сделать это число больше.