题目描述

Hao 和 Alex 是好朋友。赢得编程比赛后，他们获得了一个超大披萨作为奖品。

最初披萨被分成 $n$ 个切片。每一天按如下过程进行：

• 若剩余切片数不超过 $2$，Alex 吃掉所有剩余切片，过程结束；

• 否则设当前剩余切片数为 $m$（$m\ge 3$）。Hao 将这 $m$ 个切片分成三组，大小为 $m_1,m_2,m_3$，满足

  $$m_1+m_2+m_3=m,\qquad 1\le m_1\le m_2\le m_3.$$

  然后：

  • Hao 吃掉 $m_1$ 片（最小组）；
  • Alex 吃掉 $m_2$ 片（中间组）；
  • 剩下的 $m_3$ 片（最大组）留到下一天继续处理。

Hao 每次可以自由选择如何划分（即选择合适的 $m_1,m_2,m_3$，满足上述条件）。请问：如果 Hao 每天都最优划分以使自己总共吃到的切片数最大化，那么他最终最多能吃到多少片？

输入格式

• 第一行：一个整数 $t$，表示测试用例个数（$1\le t\le 500$）。
• 随后每个测试用例占 $1$ 行，每行包含一个整数 $n$，表示初始切片数（$3\le n\le 10^9$）。

输出格式

对于每个测试用例，输出 一行，包含一个整数：Hao 能吃到的最大切片总数。

样例输入

3
8
4
3

样例输出

3
1
1

说明

样例解释

• 第一个样例（$n=8$）：一种最优策略是先分为 $2,3,3$，Hao 吃 $2$，剩 $3$；然后对剩下的 $3$ 分为 $1,1,1$，Hao 再吃 $1$，最终 Hao 吃到 $2+1=3$ 片，之后剩余 1 片被 Alex 吃掉。
• 第二个样例（$n=4$）：最优划分为 $1,1,2$，Hao 吃 $1$，剩 $2$，Alex 吃掉剩余 $2$，Hao 共吃 $1$。
• 第三个样例（$n=3$）：唯一可行的划分为 $1,1,1$，Hao 吃 $1$。