Observera den ovanliga tidsgränsen i denna uppgift.

Dvärgen Biologen har nyligen gjort ett banbrytande genombrott inom området folkloristisk genetik vid universitetet i Wrocław. Efter åratal av forskning har han framgångsrikt sekvenserat DNA från tre skilda arter som befolkar staden: dvärgar (hans egen art), tomtar (invånarna i den magiska skogen) och bronslingar (det legendariska bronsstatyfolket på Wrocławs gator).

Varje DNA-sekvens representeras som en binär sträng, där 0 betecknar en recessiv genetisk markör och 1 betecknar en dominant. Hans mål är att hitta den längsta gemensamma delsekvensen (LCS) av genetiska markörer som delas av alla tre arter — detta skulle avslöja deras gemensamma evolutionära ursprung och förklara varför de alla hamnade i Wrocław! Att beräkna den exakta LCS för tre sekvenser är dock beräkningsmässigt dyrt, och dvärgens forskningsanslag håller på att ta slut. Han behöver inte perfekt precision; han behöver bara hitta ett heltal $x$ sådant att den sanna längden på 3-LCS ligger i intervallet $[x, 2x]$. Med andra ord duger en $2$-approximation.

Denna approximation kommer att vara tillräckligt bra för hans forskningsartikel och ändå ge värdefulla insikter i det gemensamma genetiska arvet hos Wrocławs magiska invånare. Kan du hjälpa dvärgen att hitta en sådan approximation?

Indata

Den första raden i indatan innehåller talet $T$, som representerar antalet testfall.

Varje testfall består av fyra rader. Den första raden innehåller ett heltal $N$, längden på DNA-sekvenserna. De följande tre raderna innehåller binära strängar av längd $N$ som representerar DNA-sekvenserna för dvärgar, tomtar och bronslingar.

Utdata

För varje testfall, skriv ut ett enda heltal $x$ sådant att längden på den längsta gemensamma delsekvensen för de tre DNA-sekvenserna ligger i intervallet $[x, 2x]$.

Begränsningar

$1 \le T \le 10$, $1 \le N \le 3000$, varje sträng består endast av siffrorna 0 och 1.

Exempel

Indata 1

2
4
0010
0110
0101
2
10
00
01

Utdata 1

2
1

Förklaring

I det första exemplet är den optimala LCS 010, så dess längd är $3$. Därför är svaret $2$ också korrekt.