题目描述

最近，SPY 从 XCPC 退役了。他非常怀念从零开始学习算法并赢得 ICPC 金牌的时光。所以他正在寻找一个 NPY（非编程青年）作为他的接班人。SPY 非常受欢迎，有 $n$ 个 NPY 想要成为他的徒弟。由于 SPY 只需要一个 NPY，他为这 $n$ 个 NPY 设置了一个测试。规则如下：

$n$ 个 NPY 的编号从 $1$ 到 $n$。SPY 将按顺序面试这 $n$ 个 NPY。第 $i$ 个 NPY 将在第 $i$ 次面试中接受测试。面试完一个 NPY 后，SPY 会得到她的 IQ（智商）数值（一个在 $[0, 2023^{2023^{2023}}]$ 范围内的整数）。SPY 可以决定是否接受她。一旦他接受了某个 NPY，测试结束，他不会继续面试后面的 NPY。一旦他拒绝了某个 NPY，就不会再给她机会。

注意，没有两个 NPY 的 IQ 是相同的。SPY 有一个特殊的策略来找到高 IQ 的 NPY。他在测试前设定一个整数 $k$（$0 \leq k < n$）。

1. 无论前 $k$ 个 NPY 有多聪明，他都会拒绝。SPY 会记录前 $k$ 个 NPY 中最高的 IQ 值 $x$。如果 $k = 0$，则 $x = -1$。
2. 然后他将面试第 $(k + 1)$ 到第 $(n - 1)$ 个 NPY。一旦 SPY 面试到一个 IQ 高于 $x$ 的 NPY，他就会接受她并结束测试。
3. 如果没有 NPY 被接受，SPY 将接受第 $n$ 个 NPY。

$n$ 个 NPY 的 IQ 排名是随机的，这意味着他们的排名是 $1 \sim n$ 的一个排列，并且 $n!$ 种可能情况出现的概率相等。尽管 SPY 是实用算法大师，但他很难设定这个数字 $k$。你能帮他计算出，为了最大化选到 IQ 最高的 NPY 的概率，所需的最小 $k$ 值是多少吗？

输入格式

第一行包含一个整数 $T$（$1 \leq T \leq 10^{4}$），表示测试用例的数量。

接下来的 $T$ 行，每行包含一个整数 $n$（$1 \leq n \leq 10^{4}$），表示 NPY 的数量。

输出格式

对于每个测试用例，输出一行一个整数，表示整数 $k$。

8
1
2
3
4
9000
9001
9002
9003

0
0
1
1
3311
3311
3311
3312

解释 #1

在第三个测试用例中，有 $3$ 个 NPY。令数组 $p$ 表示 IQ 排名。第 $i$ 个 NPY 的 IQ 排名是 $p_i$。$p_u = 1$ 的第 $u$ 个 NPY 具有最低的 IQ，$p_v = 3$ 的第 $v$ 个 NPY 具有最高的 IQ。

共有 $3! = 6$ 种等概率出现的情况。下表显示了所有情况下被接受的 NPY 的 IQ 排名，以及选到最高 IQ NPY 的概率。