Problem Description

Define the **median** of a sequence of length $n$ as:

If $n$ is odd, the **median** is the number ranked $\lfloor \dfrac {n+1} 2\rfloor$ if we sort the sequence in ascending order.

If $n$ is even, the **median** is the number that has more occurences between the numbers ranked $\lfloor \dfrac {n} 2\rfloor$ and $\lfloor \dfrac {n} 2+1\rfloor$ if we sort the sequence in ascending order. If they appeared for the same number of times the smaller one is the **median**.

Define the **shikness** of a sequence $A$ as the number of occurences of the **median** of $A$.

Define the **nitness** of a sequence $A$ as the maximum **shikness** over all continuous subsequences of $A$.

You want to find a sequence $A$ of length $n$, satisfying $1\leq A_i\leq 3$ for every $1\le i\leq n$, with the minimum **nitness**.

Calculate the **nitness** of such sequence.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 2 \times 10 ^ 5$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 10^9$).

Output

For each test case, print a single integer - the **nitness** of such sequence.

6
1
2
3
4
5
6

1
1
1
2
2
2