El reino de Wonder tiene $n!$ ciudades. Cada ciudad se codifica con $n$ números $d_1d_2\ldots d_n$, que forman una permutación de $1,2,\ldots,n$. El castillo del reino de Wonder está en la ciudad codificada como $1,2,\ldots,n$. Sean $a_1a_2\ldots a_n$ y $b_1b_2\ldots b_n$ los códigos de las ciudades $A$ y $B$, respectivamente. Hay una carretera de longitud $1$ entre las ciudades $A$ y $B$ del reino si y solo si existe un $i$, $1\le i<n$, que cumple las dos condiciones siguientes:

1. $a_i=b_{i+1}$ y $b_i=a_{i+1}$;

2. $a_j=b_j$ para $j\in\{1,2,\ldots,n\}\setminus\{i,i+1\}$.

Un día el rey invita a todos los alcaldes a una reunión en el castillo. Ayuda a los alcaldes a calcular la distancia que deben recorrer hasta el castillo. Observa que la ciudad del castillo se codifica como $1,2,3,\ldots,n$.

Veamos el siguiente ejemplo. Hay 6 ciudades en el reino. Cada ciudad se codifica con una permutación de $1,2,3$.

Entrada

La primera línea contiene un entero $m$ que representa el número de casos de prueba. Cada caso de prueba que sigue consta de dos líneas. La primera línea de cada caso contiene un entero $n$, $3\le n\le100$, que indica que hay $n!$ ciudades en el reino. La segunda línea contiene $n$ números distintos de $\{1,2,\ldots,n\}$, separados por espacios, que indican el código de la ciudad dada.

Restricciones

• $1\le m\le50$.

• $1\le n\le100$.

Salida

Para cada caso de prueba, muestra una línea con un entero que indique la distancia entre la ciudad dada y el castillo.

Ejemplos

Entrada 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

Salida 1

2
6
3
8
9