この問題の通常とは異なる実行時間制限に注意してください。

生物学者ドワーフは最近、ヴロツワフ大学の民俗遺伝学の分野で画期的な発見をしました。長年の研究の末、彼は街に生息する $3$ つの異なる種族、すなわちドワーフ（彼自身の種族）、ノーム（魔法の森の住人）、およびブロンズリング（ヴロツワフの街角にある伝説のブロンズ像の民）の DNA 配列の解読に成功しました。

各 DNA 配列はバイナリ文字列として表され、0 は劣性（潜性）の遺伝マーカーを、1 は優性（顕性）の遺伝マーカーを表します。彼の目標は、$3$ つの種族すべてに共通する遺伝マーカーの最長共通部分列（LCS）を見つけることです。これにより、彼らの共通の進化的祖先が明らかになり、なぜ彼ら全員がヴロツワフにたどり着いたのかが説明できるでしょう！しかし、$3$ つの配列の厳密な LCS を計算することは計算コストが高く、ドワーフの研究助成金は底をつきかけています。彼は完璧な精度を必要としていません。真の 3-LCS の長さが区間 $[x, 2x]$ に収まるような整数 $x$ を見つけるだけでよいのです。言い換えれば、$2$-近似で十分です。

この近似は彼の研究論文にとって十分に良く、ヴロツワフの魔法の住人たちの共通の遺伝的遺産に関する貴重な洞察を与えてくれるでしょう。ドワーフがそのような近似を見つけるのを手伝ってくれますか？

入力

入力の $1$ 行目には、テストケースの数を表す数値 $T$ が含まれます。

各テストケースは $4$ 行からなります。$1$ 行目には、DNA 配列の長さを表す整数 $N$ が含まれます。続く $3$ 行には、ドワーフ、ノーム、ブロンズリングの DNA 配列を表す長さ $N$ のバイナリ文字列が含まれます。

出力

各テストケースについて、$3$ つの DNA 配列の最長共通部分列の長さが区間 $[x, 2x]$ に収まるような単一の整数 $x$ を出力してください。

制約

$1 \le T \le 10$、$1 \le N \le 3000$、各文字列は数字 0 と 1 のみからなります。

入出力例

入力例 1

2
4
0010
0110
0101
2
10
00
01

出力例 1

2
1

注記

最初の例では、最適な LCS は 010 であり、その長さは $3$ です。したがって、答え $2$ も正解となります。