CF1735A.Working Week

Your working week consists of $n$ days numbered from $1$ to $n$, after day $n$ goes day $1$ again. And $3$ of them are days off. One of the days off is the last day, day $n$. You have to decide when the other two are.

Choosing days off, you pursue two goals:

• No two days should go one after the other. Note that you can't make day $1$ a day off because it follows day $n$.
• Working segments framed by days off should be as dissimilar as possible in duration. More specifically, if the segments are of size $l_1$, $l_2$, and $l_3$ days long, you want to maximize $\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$.

Output the maximum value of $\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$ that can be obtained.

你的一周工作由 $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|)$。

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The only line of each test case contains the integer $n$ ($6 \le n \le 10^9$).

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$6 \le n \le 10^9$）。

For each test case, output one integer — the maximum possible obtained value.

对于每个测试用例，输出一个整数——所能获得的最大值。

In the image below you can see the example solutions for the first two test cases. Chosen days off are shown in purple. Working segments are underlined in green.

In test case $1$, the only options for days off are days $2$, $3$, and $4$ (because $1$ and $5$ are next to day $n$). So the only way to place them without selecting neighboring days is to choose days $2$ and $4$. Thus, $l_1 = l_2 = l_3 = 1$, and the answer $\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0$.

For test case $2$, one possible way to choose days off is shown. The working segments have the lengths of $2$, $1$, and $4$ days. So the minimum difference is $1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|)$. It can be shown that there is no way to make it larger.

在下面的图片中，您可以看到前两个测试用例的示例解法。所选的休息日以紫色标出，工作段则以绿色下划线标出。

在测试用例 $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|)$。可以证明，无法使该最小差值更大。