题目描述

你的工作周由 $n$ 天组成，编号从 $1$ 到 $n$，在第 $n$ 天之后又回到第 $1$ 天。其中有 $3$ 天是休息日，其中一天必须是最后一天（即第 $n$ 天）。你需要决定另外两天的休息日。

选择休息日时，你有两个目标：

• 不能有两个休息日相邻。注意，由于第 $1$ 天紧跟在第 $n$ 天之后，你不能将第 $1$ 天设为休息日。
• 由休息日分隔开的工作区间长度应尽可能不相似。更具体地说，假设这三个工作区间的长度分别为 $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$）。

输出格式

对于每个测试用例，输出一个整数，表示可以获得的最大值。

说明/提示

下图展示了前两个测试用例的示例解法。紫色表示选定的休息日，绿色下划线表示工作区间。

在第 $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|)$。可以证明没有更大的方案。

由 ChatGPT 4.1 翻译

样例

3
6
10
1033

0
1
342