Perhatikan batas waktu yang tidak biasa pada soal ini.

Kurcaci Sang Ahli Biologi baru-baru ini membuat penemuan terobosan di bidang genetika cerita rakyat di Universitas Wrocław. Setelah bertahun-tahun melakukan penelitian, ia berhasil mengurutkan DNA dari tiga spesies berbeda yang menghuni kota tersebut: kurcaci (kaumnya sendiri), gnome (penghuni hutan ajaib), dan bronzeling (kaum patung perunggu legendaris di jalanan Wrocław).

Setiap barisan DNA direpresentasikan sebagai string biner, di mana 0 menunjukkan penanda genetik resesif dan 1 menunjukkan penanda genetik dominan. Tujuannya adalah menemukan upabarisan persekutuan terpanjang (LCS) dari penanda genetik yang dimiliki bersama oleh ketiga spesies tersebut — hal ini akan mengungkap leluhur evolusi bersama mereka dan menjelaskan mengapa mereka semua berakhir di Wrocław! Namun, menghitung LCS eksak dari tiga barisan sangat mahal secara komputasi, dan dana penelitian sang kurcaci hampir habis. Ia tidak membutuhkan presisi yang sempurna; ia hanya perlu mencari sebuah bilangan bulat $x$ sedemikian sehingga panjang sebenarnya dari 3-LCS berada di dalam interval $[x, 2x]$. Dengan kata lain, sebuah $2$-aproksimasi sudah cukup.

Aproksimasi ini sudah cukup baik untuk makalah penelitiannya dan tetap memberikan wawasan berharga tentang warisan genetik bersama dari para penghuni ajaib Wrocław. Bisakah Anda membantu sang kurcaci menemukan aproksimasi semacam itu?

Masukan

Baris pertama masukan berisi bilangan $T$, yang menyatakan jumlah kasus uji.

Setiap kasus uji terdiri dari empat baris. Baris pertama berisi sebuah bilangan bulat $N$, yaitu panjang barisan DNA. Tiga baris berikutnya berisi string biner dengan panjang $N$ yang menyatakan barisan DNA dari kurcaci, gnome, dan bronzeling.

Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat $x$ sedemikian sehingga panjang dari upabarisan persekutuan terpanjang dari ketiga barisan DNA berada di dalam interval $[x, 2x]$.

Batasan

$1 \le T \le 10$, $1 \le N \le 3000$, setiap string hanya terdiri dari digit 0 dan 1.

Contoh

Masukan 1

2
4
0010
0110
0101
2
10
00
01

Keluaran 1

2
1

Catatan

Pada contoh pertama, LCS optimal adalah 010, sehingga panjangnya adalah $3$. Oleh karena itu jawaban $2$ juga benar.