浩和亚历克斯是好朋友。一起赢得编程比赛后,他们获得了一个巨大的披萨作为奖品。
最初,他们得到 $$$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可以吃的最大切片总数。
示例
输入复制
3843
输出复制
311
注意
在第一个测试用例中,Hao 可以吃 $$$3$$$ 片,如下所示:
- 分为 $$$m_1 = 2$$$、$$$m_2 = 3$$$ 和 $$$m_3 = 3$$$。郝吃了$$$2$$$片,亚历克斯吃了$$$3$$$片,剩下的$$$3$$$片被带到第二天。
- 分为 $$$m_1 = 1$$$、$$$m_2 = 1$$$ 和 $$$m_3 = 1$$$。 hao 吃了 $$$1$$$ 片,Alex 吃了 $$$1$$$ 片,剩下的 $$$1$$$ 片被结转到第二天。
- 只剩下$$$1$$$一片,所以亚历克斯吃了它。
在第二个测试用例中,Hao 可以吃 $$$1$$$ 片,如下所示:
- 分为 $$$m_1 = 1$$$、$$$m_2 = 1$$$ 和 $$$m_3 = 2$$$。郝吃了$$$1$$$片,亚历克斯吃了$$$1$$$片,剩下的$$$2$$$片被结转到第二天。
- 只剩下 $$$2$$$ 片,所以 Alex 把它们全部吃掉了。