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$ とする。次の 2 条件を満たす $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$ が与えられる。続く各テストケースは 2 行からなる。各テストケースの最初の行には、王国に $n!$ 個の都市があることを表す整数 $n$ ($3\le n\le100$) が与えられる。2 行目には、与えられた都市の符号を表す、$\{1,2,\ldots,n\}$ に属する相異なる $n$ 個の数が空白区切りで与えられる。

制約

• $1\le m\le50$。

• $1\le n\le100$。

出力

各テストケースについて、与えられた都市と城との距離を表す整数を 1 行に出力せよ。

入出力例

入力 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