Zwróć uwagę na nietypowy limit czasu w tym zadaniu.

Krasnolud Biolog dokonał niedawno przełomowego odkrycia w dziedzinie genetyki folklorystycznej na Uniwersytecie Wrocławskim. Po latach badań udało mu się zsekwencjonować DNA trzech odrębnych gatunków zamieszkujących miasto: krasnoludów (jego własnego gatunku), gnomów (magicznych mieszkańców lasu) oraz brązoludków (legendarnego ludu brązowych posągów z wrocławskich ulic).

Każda sekwencja DNA jest reprezentowana jako ciąg binarny, gdzie 0 oznacza recesywny marker genetyczny, a 1 oznacza marker dominujący. Jego celem jest znalezienie najdłuższego wspólnego podciągu (LCS) markerów genetycznych dzielonych przez wszystkie trzy gatunki — ujawniłoby to ich wspólne ewolucyjne pochodzenie i wyjaśniło, dlaczego wszystkie trafiły właśnie do Wrocławia! Jednak obliczenie dokładnego LCS dla trzech ciągów jest kosztowne obliczeniowo, a grant badawczy krasnoluda powoli się kończy. Nie potrzebuje on idealnej dokładności; wystarczy mu znalezienie takiej liczby całkowitej $x$, że prawdziwa długość 3-LCS leży w przedziale $[x, 2x]$. Innymi słowy, wystarczy $2$-aproksymacja.

Takie przybliżenie będzie wystarczająco dobre do jego pracy naukowej i nadal dostarczy cennych informacji na temat wspólnego dziedzictwa genetycznego magicznych mieszkańców Wrocławia. Czy pomożesz krasnoludowi znaleźć takie przybliżenie?

Wejście

Pierwszy wiersz wejścia zawiera liczbę $T$, oznaczającą liczbę zestawów testowych.

Każdy zestaw testowy składa się z czterech wierszy. Pierwszy wiersz zawiera liczbę całkowitą $N$, długość sekwencji DNA. Kolejne trzy wiersze zawierają ciągi binarne długości $N$ reprezentujące sekwencje DNA krasnoludów, gnomów oraz brązoludków.

Wyjście

Dla każdego zestawu testowego wypisz jedną liczbę całkowitą $x$ taką, że długość najdłuższego wspólnego podciągu trzech sekwencji DNA leży w przedziale $[x, 2x]$.

Ograniczenia

$1 \le T \le 10$, $1 \le N \le 3000$, każdy ciąg składa się wyłącznie z cyfr 0 oraz 1.

Przykłady

Wejście 1

2
4
0010
0110
0101
2
10
00
01

Wyjście 1

2
1

Uwaga

W pierwszym przykładzie optymalny LCS to 010, więc jego długość wynosi $3$. Zatem odpowiedź $2$ również jest poprawna.