AT_arc195_d [ARC195D] Swap and Erase

数列 $ A = (A_1,\ldots,A_N) $ があります。これに対して、以下の $ 2 $ 種類の操作を、任意の順番で任意の回数だけ行うことができます。 - 操作直前の $ A $ の長さを $ K $ とする。 $ 1\leq i\leq K-1 $ を満たす整数 $ i $ を選び、 $ A $ の第 $ i $ 項と第 $ (i+1) $ 項を入れ替える。 - 操作直前の $ A $ の長さを $ K $ とする。 $ 1\leq i\leq K $ かつ $ A $ の第 $ 1 $ 項から第 $ i $ 項の値が全て等しいような整数 $ i $ を選び、 $ A $ の第 $ 1 $ 項から第 $ i $ 項までを全て削除する。 $ A $ を空の数列にするために必要な合計操作回数の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、以下の $ 3 $ 回の操作によって $ A $ を空の数列にすることができます。 - $ A $ の第 $ 3 $ 項と第 $ 4 $ 項を入れ替える。結果として、 $ A $ は $ (1,1,1,2,2) $ となる。 - $ A $ の第 $ 1 $ 項から第 $ 3 $ 項までを削除する。結果として、 $ A $ は $ (2,2) $ となる。 - $ A $ の第 $ 1 $ 項から第 $ 2 $ 項までを削除する。結果として、 $ A $ は空の数列となる。 $ 2 $ 番目のテストケースについて、 $ A $ の第 $ 1 $ 項を削除する操作を $ 4 $ 回行うことで $ A $ を空の数列にすることができます。また、 $ 3 $ 回以下の操作では $ A $ を空の数列にすることはできません。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq N $ - すべてのテストケースにわたる $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力される値は全て整数