EPS.AC はこのコンテストの作問チームです。そのメンバーは Colin、Claris、Little_Sheep_Yawn です。

彼らはこのコンテストのために $n$ 問の候補問題を用意しました。各メンバーは、自分の判断に従ってこれら $n$ 問を易しい順に並べます。コンテストの難易度のバランスを取り、異なる実力の参加者を区別できるようにするため、彼らはこれらの問題を、易しいものから難しいものへと順序付けられた難易度の階層に分けたいと考えています。各問題はちょうど一つの階層に属さなければなりません。同じ階層内の問題には難易度による順序を付けず、各階層には少なくとも一問が含まれなければなりません。

階層を、易しいものから難しいものへと左から右に並べます。連続する二つの階層の間の境界について、その左側には境界より前の階層に属するすべての問題があり、右側には境界より後の階層に属するすべての問題があります。あるメンバーの順位付けにおいて、左側のすべての問題が右側のすべての問題より前に現れるなら、そのメンバーはこの境界を支持するといいます。

すべての境界が少なくとも二人のメンバーに支持されているとき、階層への分割は有効です。境界ごとに支持するメンバーが異なっていてもかまいません。

難易度の階層が多いほど、よりよい作問になります。彼らがよいコンテストを作れるように、階層の個数の最大値を求めてください。

入力

入力は複数のテストケースからなります。最初の行には、テストケースの数を表す整数 $t$（$1\le t\le 2\times 10^5$）が与えられます。

各テストケースについて：

• 最初の行には整数 $n$（$1\le n\le 2\times 10^5$）が与えられます。
• 続く三行には、それぞれ $1,2,\ldots,n$ の順列が与えられ、順に Colin、Claris、Little_Sheep_Yawn の順位付けを表します。

すべてのテストケースにわたる $n$ の合計は $2\times 10^5$ 以下であることが保証されます。

出力

各テストケースについて、階層の個数の最大値を出力してください。

入出力例

入力 1

3
6
2 1 4 5 6 3
1 2 3 4 5 6
3 1 4 2 6 5
4
1 3 2 4
1 2 4 3
2 1 3 4
3
1 2 3
2 3 1
3 1 2

出力 1

3
4
1

注記

最初のテストケースでは、問題を、易しい順に $\{1,2\},\{3,4\},\{5,6\}$ という三つの階層に分けられます。Colin と Claris は最初の境界を支持し、Claris と Little_Sheep_Yawn は二つ目の境界を支持します。この分割は最適です。

二つ目のテストケースでは、四つの問題をそれぞれ独立した階層にして、易しい順に $\{1\},\{2\},\{3\},\{4\}$ と並べられます。三つの境界は、順に Colin と Claris、Claris と Little_Sheep_Yawn、Colin と Little_Sheep_Yawn に支持されます。

三つ目のテストケースでは、有効な境界が存在しないため、すべての問題を一つの階層に入れなければなりません。