Wonder 왕국에는 $n!$개의 도시가 있다. 각 도시는 $1,2,\ldots,n$의 순열인 $n$개의 수 $d_1d_2\ldots d_n$으로 표현된다. Wonder 왕국의 성은 $1,2,\ldots,n$으로 표현되는 도시에 있다. 도시 $A$와 $B$의 코드를 각각 $a_1a_2\ldots a_n$과 $b_1b_2\ldots 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,\ldots,n\}\setminus\{i,i+1\}$에 대해 $a_j=b_j$이다.

어느 날 왕은 모든 시장을 성에서 열리는 회의에 초대한다. 시장들이 성까지 이동해야 하는 거리를 계산하도록 도와주어라. 성이 있는 도시의 코드는 $1,2,3,\ldots,n$임에 유의하라.

다음 예를 보자. 왕국에 6개의 도시가 있고 각 도시는 $1,2,3$의 순열로 표현된다.

입력

첫 줄에는 테스트 케이스 수를 나타내는 정수 $m$이 주어진다. 이어지는 각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫 줄에는 왕국에 $n!$개의 도시가 있음을 나타내는 정수 $n$ ($3\le n\le100$)이 주어진다. 두 번째 줄에는 주어진 도시의 코드를 나타내는, $\{1,2,\ldots,n\}$에 속하는 서로 다른 $n$개의 수가 공백으로 구분되어 주어진다.

제한

• $1\le m\le50$.

• $1\le n\le100$.

출력

각 테스트 케이스에 대해 주어진 도시와 성 사이의 거리를 나타내는 정수 하나를 한 줄에 출력하라.

예제

입력 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