Huomaa tämän tehtävän poikkeuksellinen aikaraja.

Biologikääpiö on äskettäin tehnyt uraauurtavan löydön kansanperinnegenetiikan alalla Wrocławin yliopistossa. Vuosien tutkimuksen jälkeen hän on onnistunut sekvensoimaan kaupungissa asuvan kolmen eri lajin DNA:n: kääpiöiden (hänen oman lajinsa), maahisten (taikametsän asukkaiden) ja pronssilaisten (Wrocławin katujen legendaarisen pronssipatsasväen).

Jokainen DNA-sekvenssi esitetään binäärijonona, jossa 0 tarkoittaa peittyvää geneettistä merkkiä ja 1 vallitsevaa. Hänen tavoitteenaan on löytää kaikkien kolmen lajin jakamien geneettisten merkkien pisin yhteinen alijono (LCS) — tämä paljastaisi heidän yhteisen evolutiivisen alkuperänsä ja selittäisi, miksi he kaikki päätyivät Wrocławiin! Kolmen jonon tarkan LCS:n laskeminen on kuitenkin laskennallisesti raskasta, ja kääpiön tutkimusapuraha on loppumassa. Hän ei tarvitse täydellistä tarkkuutta; hänen tarvitsee vain löytää kokonaisluku $x$ siten, että 3-LCS:n todellinen pituus kuuluu välille $[x, 2x]$. Toisin sanoen $2$-approksimaatio riittää.

Tämä approksimaatio on riittävän hyvä hänen tutkimusartikkeliinsa ja tarjoaa silti arvokasta tietoa Wrocławin taianomaisten asukkaiden yhteisestä geneettisestä perimästä. Voitko auttaa kääpiötä löytämään tällaisen approksimaation?

Syöte

Syötteen ensimmäinen rivi sisältää luvun $T$, joka kuvaa testitapausten lukumäärää.

Jokainen testitapaus koostuu neljästä rivistä. Ensimmäinen rivi sisältää kokonaisluvun $N$, DNA-sekvenssien pituuden. Seuraavat kolme riviä sisältävät pituutta $N$ olevat binäärijonot, jotka kuvaavat kääpiöiden, maahisten ja pronssilaisten DNA-sekvenssejä.

Tuloste

Tulosta jokaista testitapausta kohden yksi kokonaisluku $x$ siten, että kolmen DNA-sekvenssin pisimmän yhteisen alijonon pituus kuuluu välille $[x, 2x]$.

Rajoitukset

$1 \le T \le 10$, $1 \le N \le 3000$, jokainen merkkijono koostuu vain numeroista 0 ja 1.

Esimerkit

Syöte 1

2
4
0010
0110
0101
2
10
00
01

Tuloste 1

2
1

Huomautus

Ensimmäisessä esimerkissä optimaalinen LCS on 010, joten sen pituus on $3$. Täten myös vastaus $2$ on oikein.