Takið eftir óvenjulegu tímatakmarki í þessu verkefni.

Líffræðingurinn Dvergur hefur nýlega gert tímamótauppgötvun á sviði þjóðsagnierfðafræði við Háskólann í Wrocław. Eftir áralangar rannsóknir hefur honum tekist að raðgreina DNA þriggja ólíkra tegunda sem búa í borginni: dverga (hans eigin tegundar), álfa (íbúa töfraskógarins) og bronsunga (hins goðsagnakennda bronsstyttufólks á götum Wrocław).

Hver DNA-röð er táknuð sem tvíundarstrengur, þar sem 0 táknar víkjandi erfðamark og 1 táknar ríkjandi erfðamark. Markmið hans er að finna lengstu sameiginlegu hlutrunu (LCS) erfðamarka sem allar þrjár tegundirnar deila — það myndi leiða í ljós sameiginlegan þróunarlegan uppruna þeirra og útskýra hvers vegna þau enduðu öll í Wrocław! Hins vegar er reikningslega dýrt að finna nákvæmt LCS þriggja runa og rannsóknarstyrkur dvergsins erเกือบ á þrotum. Hann þarf ekki fullkomna nákvæmni; hann þarf bara að finna heiltölu $x$ þannig að raunveruleg lengd 3-LCS liggi á bilinu $[x, 2x]$. Með öðrum orðum, $2$-nálgun dugar.

Þessi nálgun verður nógu góð fyrir rannsóknargreinina hans og mun samt veita dýrmæta innsýn í sameiginlega erfðaarfleifð töfraíbúa Wrocław. Geturðu hjálpað dvergnum að finna slíka nálgun?

Inntak

Fyrsta lína inntaksins inniheldur töluna $T$, sem táknar fjölda prófunartilfella.

Hvert prófunartilfelli samanstendur af fjórum línum. Fyrsta línan inniheldur heiltölu $N$, lengd DNA-raðanna. Næstu þrjár línur innihalda tvíundarstrengi af lengd $N$ sem tákna DNA-raðir dverga, álfa og bronsunga.

Úttak

Fyrir hvert prófunartilfelli skaltu prenta eina heiltölu $x$ þannig að lengd lengstu sameiginlegu hlutrunu DNA-raðanna þriggja liggi á bilinu $[x, 2x]$.

Takmarkanir

$1 \le T \le 10$, $1 \le N \le 3000$, hver strengur samanstendur eingöngu af tölustöfunum 0 og 1.

Dæmi

Inntak 1

2
4
0010
0110
0101
2
10
00
01

Úttak 1

2
1

Athugasemd

Í fyrsta dæminu er besta LCS 010, svo lengd þess er $3$. Því er svarið $2$ einnig rétt.