Hao and Alex are good friends. After winning a coding competition together, they received a huge pizza as their prize.

Initially, they are given $n$ slices of pizza. Each day, the following process takes place:

• If there are at most $2$ slices remaining, Alex eats all of them.

• Otherwise, let $m$ be the current number of slices ($m\ge 3$). Hao splits them into three groups of sizes $m_1$, $m_2$, and $m_3$ such that:

  $$m_1 + m_2 + m_3 = m\text{ and } 1 \le m_1\le m_2\le m_3.$$</p><p>Then:</p><ul> <li> Hao eats$m\_1$slices (the smallest group). </li><li> Alex eats$m\_2$slices (the middle group). </li><li> The remaining$m\_3$ slices (the largest group) are carried over to the next day.$$

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first and only line of each test case contains a single integer $n$ ($3 \le n \le 10^9$) — the initial number of pizza slices.

Note that there are no constraints on the sum of $n$ over all test cases.

Output

For each test case, output a single integer representing the maximum total number of slices Hao can eat.

Note

In the first test case, Hao can eat $3$ slices as follows:

1. Split into $m_1 = 2$, $m_2 = 3$, and $m_3 = 3$. Hao eats $2$ slices, Alex eats $3$ slices, and the remaining $3$ slices are carried over to the next day.
2. Split into $m_1 = 1$, $m_2 = 1$, and $m_3 = 1$. Hao eats $1$ slice, Alex eats $1$ slice, and the remaining $1$ slice is carried over to the next day.
3. Only $1$ slice remains, so Alex eats it.

In the second test case, Hao can eat $1$ slice as follows:

1. Split into $m_1 = 1$, $m_2 = 1$, and $m_3 = 2$. Hao eats $1$ slice, Alex eats $1$ slice, and the remaining $2$ slices are carried over to the next day.
2. Only $2$ slices remain, so Alex eats them all.

Samples

3
8
4
3

3
1
1