Beachte das ungewöhnliche Zeitlimit bei dieser Aufgabe.

Zwerg der Biologe hat kürzlich an der Universität Breslau (Wrocław) eine bahnbrechende Entdeckung auf dem Gebiet der Folklore-Genetik gemacht. Nach jahrelanger Forschung ist es ihm gelungen, die DNA von drei verschiedenen Spezies zu sequenzieren, die die Stadt bewohnen: Zwerge (seine eigene Art), Gnome (die Bewohner des magischen Waldes) und Bronzelinge (das legendäre Volk der Bronzestatuen auf den Straßen Breslaus).

Jede DNA-Sequenz wird als Binärstring dargestellt, wobei 0 für einen rezessiven genetischen Marker und 1 für einen dominanten steht. Sein Ziel ist es, die längste gemeinsame Teilfolge (LCS) genetischer Marker zu finden, die alle drei Spezies teilen — dies würde ihre gemeinsame evolutionäre Abstammung enthüllen und erklären, warum sie alle in Breslau gelandet sind! Die Berechnung der exakten LCS von drei Sequenzen ist jedoch rechenintensiv, und das Forschungsstipendium des Zwergs geht zur Neige. Er braucht keine perfekte Präzision; er muss lediglich eine ganze Zahl $x$ finden, sodass die wahre Länge der 3-LCS im Intervall $[x, 2x]$ liegt. Mit anderen Worten, eine $2$-Approximation reicht völlig aus.

Diese Approximation ist gut genug für seine Forschungsarbeit und liefert dennoch wertvolle Einblicke in das gemeinsame genetische Erbe der magischen Bewohner Breslaus. Kannst du dem Zwerg helfen, eine solche Approximation zu finden?

Eingabe

Die erste Zeile der Eingabe enthält die Zahl $T$, die Anzahl der Testfälle.

Jeder Testfall besteht aus vier Zeilen. Die erste Zeile enthält eine ganze Zahl $N$, die Länge der DNA-Sequenzen. Die nächsten drei Zeilen enthalten Binärstrings der Länge $N$, welche die DNA-Sequenzen der Zwerge, Gnome und Bronzelinge darstellen.

Ausgabe

Gib für jeden Testfall eine einzige ganze Zahl $x$ aus, sodass die Länge der längsten gemeinsamen Teilfolge der drei DNA-Sequenzen im Intervall $[x, 2x]$ liegt.

Einschränkungen

$1 \le T \le 10$, $1 \le N \le 3000$, jeder String besteht nur aus den Ziffern 0 und 1.

Beispiele

Eingabe 1

2
4
0010
0110
0101
2
10
00
01

Ausgabe 1

2
1

Hinweis

Im ersten Beispiel ist die optimale LCS 010, ihre Länge beträgt also $3$. Daher ist die Antwort $2$ ebenfalls korrekt.