奇迹王国拥有 $n!$ 座城市。每座城市都由一个 $n$ 个数字组成的序列 $d_1 d_2 \dots d_n$ 编码，该序列是 $1, 2, \dots, n$ 的一个排列。奇迹王国的城堡位于编码为 $1, 2, \dots, n$ 的城市。设城市 $A$ 和 $B$ 的编码分别为 $a_1 a_2 \dots a_n$ 和 $b_1 b_2 \dots b_n$。当且仅当存在一个 $i$（$1 \le i < n$）满足以下两个条件时，王国中城市 $A$ 和 $B$ 之间会修建一条距离为 1 的道路：

1. $a_i = b_{i+1}$ 且 $b_i = a_{i+1}$；
2. 对于所有 $j \in \{1, 2, \dots, n\} \setminus \{i, i + 1\}$，都有 $a_j = b_j$。

有一天，国王邀请所有市长到城堡开会。请帮助市长们计算他们前往城堡的旅行距离。注意，城堡所在的城市编码为 $1, 2, 3, \dots, n$。

请参考以下示例。王国中有 6 座城市。每座城市都由 $1, 2, 3$ 的一个排列进行编码。

输入格式

第一行包含一个整数 $m$，表示测试用例的数量。每个测试用例包含两行。对于每个测试用例，第一行是一个整数 $n$（$3 \le n \le 100$），表示王国中有 $n!$ 座城市；第二行包含 $n$ 个不同的数字，这些数字属于 $\{1, 2, \dots, n\}$，数字之间用空格隔开，表示给定城市的编码。

数据范围

• $1 \le m \le 50$
• $1 \le n \le 100$

输出格式

对于每个测试用例，输出一行，包含一个整数，表示给定城市与城堡之间的距离。

样例

样例输入 1

5
3
3 1 2
4
4 3 2 1
5
4 1 2 3 5
7
2 6 1 5 4 3 7
10
3 2 1 5 7 6 4 10 8 9

样例输出 1

2
6
3
8
9