有 $n$ 个人围坐在一张圆桌旁，编号为 $1$ 到 $n$。第 $i+1$ 个人坐在第 $i$ 个人的右侧（第 $1$ 个人坐在第 $n$ 个人的右侧）。

你构思了一个更好的座位安排，由排列 $p_1, p_2, \dots, p_n$ 给出。具体来说，你希望改变人们的座位，使得最终第 $p_{i+1}$ 个人坐在第 $p_i$ 个人的右侧（第 $p_1$ 个人坐在第 $p_n$ 个人的右侧）。注意，对于每种座位安排，有 $n$ 种排列可以描述它（可以通过旋转得到）。

为了实现这一目标，你可以交换相邻位置的两个人；但有一个限制：对于所有 $1 \le x \le n - 1$，你不能交换第 $x$ 个人和第 $x+1$ 个人（注意，你可以交换第 $n$ 个人和第 $1$ 个人）。实现目标所需的最小交换次数是多少？可以证明任何安排都是可以达到的。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 200\,000$)，表示坐在桌旁的人数。

第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n, p_i \neq p_j$ 当 $i \neq j$ 时)，表示桌旁人们期望的最终顺序。

所有测试用例的 $n$ 之和不超过 $200\,000$。

输出格式

对于每个测试用例，输出实现期望顺序所需的最小交换次数。

样例

输入 1

3
4
2 3 1 4
5
5 4 3 2 1
7
4 1 6 5 3 7 2

输出 1

1
10
22

说明

在第一个测试用例中，我们可以在初始配置中交换第 $4$ 个人和第 $1$ 个人（他们是相邻的），得到顺序 $[4, 2, 3, 1]$，这与期望的顺序等价。因此，在这种情况下，一次交换就足够了。