Бұл есептегі әдеттен тыс уақыт шектеуіне назар аударыңыз.

Биолог Ергежейлі жақында Вроцлав университетінде фольклорлық генетика саласында жаңалық ашты. Көпجылдық зерттеулерден кейін ол қаланы мекендейтін үш түрлі түрдің ДНҚ тізбегін сәтті анықтады: ергежейлілер (өзінің тегі), гномдар (сиқырлы орман тұрғындары) және қола адамдар (Вроцлав көшелеріндегі аңызға айналған қола мүсін-халық).

Әрбір ДНҚ тізбегі екілік жол ретінде беріледі, мұндағы 0 рецессивті генетикалық маркерді, ал 1 доминантты маркерді білдіреді. Оның мақсаты — үш түрдің барлығына ортақ генетикалық маркерлердің ең ұзын ортақ ішкі тізбегін (LCS) табу — бұл олардың ортақ эволюциялық шығу тегін ашып, неліктен олардың барлығы Вроцлавقا тап болғанын түсіндірер еді! Алайда, үш тізбектің дәл LCS-ін есептеу есептеу тұрғысынан қымбат, ал ергежейлінің зерттеу гранты таусылуға жақын. Оған мінсіз дәлдік қажет емес; оған тек 3-LCS-тің нақты ұзындығы $[x, 2x]$ кесіндісінде жататындай бүтін $x$ санын табу жеткілікті. Басқаша айтқанда, $2$-жуықтау жарайды.

Бұл жуықтау оның ғылыми мақаласы үшін жеткілікті жақсы болады және Вроцлавтың сиқырлы тұрғындарының ортақ генетикалық мұрасы туралы құнды түсінік береді. Ергежейліге осындай жуықтауды табуға көмектесе аласыз ба?

Кіріс деректері

Кіріс деректерінің бірінші жолында тест жағдайларының санын білдіретін $T$ саны берілген.

Әрбір тест жағдайы төрт жолдан тұрады. Бірінші жолда ДНҚ тізбектерінің ұзындығы болып табылатын бүтін $N$ саны берілген. Келесі үш жолда ергежейлілердің, гномдардың және қола адамдардың ДНҚ тізбектерін білдіретін ұзындығы $N$ екілік жолдар берілген.

Шығыс деректері

Әрбір тест жағдайы үшін үш ДНҚ тізбегінің ең ұзын ортақ ішкі тізбегінің ұзындығы $[x, 2x]$ кесіндісінде жататындай бір бүтін $x$ санын шығарыңыз.

Шектеулер

$1 \le T \le 10$, $1 \le N \le 3000$, әрбір жол тек 0 және 1 цифрларынан тұрады.

Мысалдар

Кіріс 1

2
4
0010
0110
0101
2
10
00
01

Шығыс 1

2
1

Ескертпе

Бірінші мысалда тиімді LCS — 010, сондықтан оның ұзындығы $3$-ке тең. Демек, $2$ жауабы да дұрыс.