← 返回题目列表

Codeforces · 1735/A

A. 工作周

中文机器翻译题面 查看原题

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

输出

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

示例

输入 #1

3
6
10
1033

输出 #1

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|)$$$。可以证明,没有办法让它变大。