← 返回题目列表

Codeforces · 2156/A

A. 披萨时间

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

浩和亚历克斯是好朋友。一起赢得编程比赛后,他们获得了一个巨大的披萨作为奖品。

最初,他们得到 $$$n$$$ 片披萨。每天都会发生以下过程:

  • 如果最多剩下 $$$2$$$ 片,Alex 会把它们全部吃掉。
  • 否则,令 $$$m$$$ 为当前切片数 ($$$m\ge 3$$$)。 hao 将它们分为三组大小 $$$m_1$$$、$$$m_2$$$ 和 $$$m_3$$$,这样:

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

    然后:

    • Hao 吃了 $$$m_1$$$ 片(最小组)。
    • Alex 吃了 $$$m_2$$$ 片(中间组)。
    • 剩余的 $$$m_3$$$ 切片(最大的组)将结转到第二天。

你的任务是确定如果Hao总是选择最佳分区,他可以吃的最大切片总数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^9$$$) — 披萨片的初始数量。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出一个整数,表示Hao可以吃的最大切片总数。

示例

输入
复制

3
8
4
3

输出
复制

3
1
1

注意

在第一个测试用例中,Hao 可以吃 $$$3$$$ 片,如下所示:

  1. 分为 $$$m_1 = 2$$$、$$$m_2 = 3$$$ 和 $$$m_3 = 3$$$。郝吃了$$$2$$$片,亚历克斯吃了$$$3$$$片,剩下的$$$3$$$片被带到第二天。
  2. 分为 $$$m_1 = 1$$$、$$$m_2 = 1$$$ 和 $$$m_3 = 1$$$。 hao 吃了 $$$1$$$ 片,Alex 吃了 $$$1$$$ 片,剩下的 $$$1$$$ 片被结转到第二天。
  3. 只剩下$$$1$$$一片,所以亚历克斯吃了它。

在第二个测试用例中,Hao 可以吃 $$$1$$$ 片,如下所示:

  1. 分为 $$$m_1 = 1$$$、$$$m_2 = 1$$$ 和 $$$m_3 = 2$$$。郝吃了$$$1$$$片,亚历克斯吃了$$$1$$$片,剩下的$$$2$$$片被结转到第二天。
  2. 只剩下 $$$2$$$ 片,所以 Alex 把它们全部吃掉了。