我们按如下方式定义数组 $a_1,a_2,\ldots,a_n$ 的“消化”操作：

• 选择任意一个长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$（即由 $1$ 到 $n$ 的整数组成，且每个整数恰好出现一次的数组）。
• 同时执行 $a_i:=a_i\bmod\max(a_{p_i},1)$。
• 选择任意一个数 $a_i$，将它从数组中删除，把其余元素连接成新的数组 $a_1,a_2,\ldots,a_{n-1}$。这个数组就是消化操作的结果。

任何能通过上述过程得到的数组，都可以作为消化操作的结果。

给定一个由 $1$ 到 $n$ 的整数组成的数组 $a_1,a_2,\ldots,a_n$。对这个数组连续进行 $n-1$ 次消化操作后，$a_1$ 能达到的最大值是多少？

输入格式

每个测试包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。接下来的各行描述这些测试用例。

每组测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$），表示数组 $a$ 的长度。

每组测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$），表示数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试用例，输出 $a_1$ 能达到的最大值。

样例

输入格式 1

1
3
3 2 2

输出格式 1

1