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

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

注意，没有两位 NPY 的 IQ 是相同的。SPY 有一种特殊的策略来寻找高 IQ 的 NPY。他在测试前设定一个整数 $k$ ($0 \le 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 \le T \le 10^4$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示 NPY 的数量。

输出格式

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

样例

输入样例 1

8
1
2
3
4
9000
9001
9002
9003

输出样例 1

0
0
1
1
3311
3311
3311
3312

说明

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

共有 $3! = 6$ 种情况，发生的概率相等。下表展示了在所有情况下被录用的 NPY 的 IQ 排名，以及录用 IQ 最高者的概率。