Merk deg den uvanlige tidsgrensen i denne oppgaven.

Dvergen Biologen har nylig gjort et banebrytende gjennombrudd innen folkloristisk genetikk ved Universitetet i Wrocław. Etter mange års forskning har han klart å sekvensere DNA-et til tre forskjellige arter som bor i byen: dverger (hans egen art), gnomer (innbyggerne i den magiske skogen) og bronselinger (det legendariske bronsestatuefolket i Wrocławs gater).

Hver DNA-sekvens representeres som en binær streng, der 0 betegner en recessiv genetisk markør og 1 betegner en dominant. Målet hans er å finne den lengste felles delsekvensen (LCS) av genetiske markører som deles av alle de tre artene — dette vil avsløre deres felles evolusjonære opphav og forklare hvorfor de alle endte opp i Wrocław! Å beregne den eksakte LCS-en for tre sekvenser er imidlertid beregningsmessig krevende, og dvergens forskningsmidler er i ferd med å ta slutt. Han trenger ikke perfekt presisjon; han trenger bare å finne et heltall $x$ slik at den sanne lengden på 3-LCS ligger i intervallet $[x, 2x]$. Med andre ord vil en $2$-approksimasjon holde.

Denne approksimasjonen vil være god nok for forskningsartikkelen hans og likevel gi verdifull innsikt i den felles genetiske arven til Wrocławs magiske innbyggere. Kan du hjelpe dvergen med å finne en slik approksimasjon?

Inndata

Den første linjen i inndataene inneholder tallet $T$, som representerer antallet testtilfeller.

Hvert testtilfelle består av fire linjer. Den første linjen inneholder et heltall $N$, lengden på DNA-sekvensene. De neste tre linjene inneholder binære strenger av lengde $N$ som representerer DNA-sekvensene til dverger, gnomer og bronselinger.

Utdata

For hvert testtilfelle skal du skrive ut ett enkelt heltall $x$ slik at lengden på den lengste felles delsekvensen for de tre DNA-sekvensene ligger i intervallet $[x, 2x]$.

Begrensninger

$1 \le T \le 10$, $1 \le N \le 3000$, hver streng består kun av sifrene 0 og 1.

Eksempler

Inndata 1

2
4
0010
0110
0101
2
10
00
01

Utdata 1

2
1

Forklaring

I det første eksempelet er den optimale LCS-en 010, så lengden er $3$. Derfor er svaret $2$ også riktig.