SPY finding NPY

Problem Description

Recently, SPY has retired from XCPC. He cherishes the memory of learning algorithms from scratch and winning the ICPC gold medal. So he is finding an NPY (non-programming youth) to be his successor. SPY is so popular that $n$ NPYs want to be his apprentice. As SPY only needs one NPY, he sets a test for the $n$ NPYs. The rules are as follows: $n$ NPYs are indexed from $1$ to $n$. SPY will interview the $n$ NPYs in order. The $i$-th NPY will be tested in the $i$-th interview. After an NPY is interviewed, SPY will get her IQ (intelligence quotient) number (an integer in $[0,2023^{2023^{2023}}]$) . SPY can decide whether to accept her or not. Once he accepts an NPY, the test would be finished and he won't interview the following NPYs. Once he refuses an NPY, he won't give her another chance. Notice that there are no two NPYs with the same IQ. SPY has a specital strategy to find an NPY with high IQ. He sets an integer $k$ $(0\leq k < n)$ before the test. 1、No matter how intelligent the first $k$ NPYs are, they will be refused. SPY will record the highest IQ number $x$ within the first $k$ NPYs. If $k=0$ then $x=-1$. 2、Then he will interview the $(k+1)$-th to the $(n-1)$-th NPY. Once SPY interviews an NPY with IQ higher than $x$, he will accept her and finish the test. 3、If no NPY is accepted, SPY will accept the $n$-th NPY. The IQ rank of the $n$ NPYs is random, which means their rank is a permutation of $1\sim n$, and the $n!$ possible situations occur with equal probability. Althouth SPY is a master of useful algorithms, it is difficult for him to set the number $k$. Can you help him to calculate the minimum $k$ to maximize the probability to accept the NPY with the highest IQ?

Input

The first line contains a single integer $T$ $(1\leq T \leq 10^4)$, indicating the number of test cases. The next $T$ lines, each line contains a single integer $n$ $(1\leq n \leq 10^4)$, indicating the number of NPYs.

Output

For each test, you should output one integer in a line, indicating the integer $k$.

Sample Input

8
1
2
3
4
9000
9001
9002
9003

Sample Output

0
0
1
1
3311
3311
3311
3312

Hint

In the third test, there are $3$ NPYs. Let the array $p$ represent to the IQ rank. The IQ rank of $i$-th NPY is $p_i$. The $u$-th NPY with $p_u=1$ has the lowest IQ, and the $v$-th NPY with $p_v=3$ has the highest IQ. There are $3!=6$ situations occur with equal probability. The following list shows the IQ rank of the accepted NPY in all situations, and the probability to accept the NPY with the highest IQ.

Source

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