D. Medians Strike Back

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.

Sample Input

6
1
2
3
4
5
6

Sample Output

1
1
1
2
2
2

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）