题目描述

有 $N$ 个人参加了一个往返比赛，比赛地点之间来回。记录了关于这场比赛的以下信息。

• 任意两个人的出发时间不同，第 $i$ 个人 $(1 \\leq i \\leq N)$ 的出发时间排名第 $i$。
• 任意两个人的往返时间（出发时间和返回时间之和）不同，第 $i$ 个人的往返时间排名第 $P_i$。
• 得到最快返回时间的人（或多人）将被授予最快返回奖。

这里，$P_1, P_2, \\dots, P_N$ 是 $1, 2, \\dots, N$ 的一个排列。

有 $T$ 个测试用例。回答每个测试用例。

约束条件

• $1 \\leq T \\leq 500$
• $2 \\leq N \\leq 10^3$
• $P_1, P_2, \\dots, P_N$ 是 $1, 2, \\dots, N$ 的一个排列。
• 所有输入值都是整数。
• 单个输入中所有测试用例的 $N$ 之和至多为 $10^3$。

输入

从标准输入读取输入，其格式如下：

$T$ $\\mathrm{case}_1$ $\\vdots$ $\\mathrm{case}_T$

每个测试用例 $\\mathrm{case}_i\\ (1 \\leq i \\leq T)$ 的格式如下：

$N$ $P_1$ $P_2$ $\\cdots$ $P_N$

输出

打印 $T$ 行。第 $i$ 行 $(1 \\leq i \\leq T)$ 应包含第 $i$ 个测试用例的答案。

示例输入 1

3
2
2 1
4
1 2 3 4
20
13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17

示例输出 1

1
4
7

• 在第一个测试用例中，有两个人参加比赛，第二个人在返回途中超过了第一个人。在这种情况下，最快返回奖授予给第二个人。
• 在第二个测试用例中，返回途中排名没有改变，因此任何人都有可能获得最快返回奖。