Królestwo Wonder ma $n!$ miast. Każde miasto jest zakodowane za pomocą $n$ liczb $d_1d_2\ldots d_n$, będących permutacją $1,2,\ldots,n$. Zamek królestwa Wonder znajduje się w mieście o kodzie $1,2,\ldots,n$. Niech $a_1a_2\ldots a_n$ i $b_1b_2\ldots b_n$ będą odpowiednio kodami miast $A$ i $B$. Droga o długości $1$ łączy miasta $A$ i $B$ w królestwie wtedy i tylko wtedy, gdy istnieje $i$, $1\le i<n$, spełniające następujące dwa warunki:

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

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

Pewnego dnia król zaprasza wszystkich burmistrzów na spotkanie w zamku. Pomóż burmistrzom obliczyć odległość, którą muszą przebyć do zamku. Zauważ, że miasto z zamkiem ma kod $1,2,3,\ldots,n$.

Spójrz na poniższy przykład. W królestwie jest 6 miast. Każde miasto jest zakodowane jako permutacja $1,2,3$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $m$ oznaczającą liczbę przypadków testowych. Każdy z kolejnych przypadków testowych składa się z dwóch wierszy. Pierwszy wiersz przypadku zawiera liczbę całkowitą $n$, $3\le n\le100$, oznaczającą, że w królestwie jest $n!$ miast. Drugi wiersz zawiera $n$ różnych liczb ze zbioru $\{1,2,\ldots,n\}$, oddzielonych spacjami, określających kod podanego miasta.

Ograniczenia

• $1\le m\le50$.

• $1\le n\le100$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą odległość między podanym miastem a zamkiem.

Przykład

Wejście 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

Wyjście 1

2
6
3
8
9