Nota il limite di tempo insolito in questo problema.

Il Nano Biologo ha recentemente fatto una scoperta rivoluzionaria nel campo della genetica folkloristica presso l'Università di Breslavia (Wrocław). Dopo anni di ricerca, è riuscito a sequenziare con successo il DNA di tre specie distinte che abitano la città: i nani (la sua stessa specie), gli gnomi (gli abitanti della foresta magica) e i bronzeling (il leggendario popolo delle statue di bronzo delle strade di Breslavia).

Ogni sequenza di DNA è rappresentata come una stringa binaria, dove 0 indica un marcatore genetico recessivo e 1 ne indica uno dominante. Il suo obiettivo è trovare la più lunga sottosequenza comune (LCS) di marcatori genetici condivisi tra tutte e tre le specie — questo rivelerebbe la loro comune ascendenza evolutiva e spiegherebbe perché sono finiti tutti a Breslavia! Tuttavia, calcolare l'esatta LCS di tre sequenze è computazionalmente costoso e i fondi di ricerca del nano stanno per esaurirsi. Non ha bisogno di una precisione perfetta; gli basta trovare un intero $x$ tale che la vera lunghezza della 3-LCS cada nell'intervallo $[x, 2x]$. In altre parole, una $2$-approssimazione andrà benissimo.

Questa approssimazione sarà abbastanza buona per il suo articolo di ricerca e fornirà comunque preziose intuizioni sul patrimonio genetico condiviso degli abitanti magici di Breslavia. Puoi aiutare il nano a trovare una tale approssimazione?

Input

La prima riga di input contiene il numero $T$, che rappresenta il numero di casi di test.

Ogni caso di test è composto da quattro righe. La prima riga contiene un intero $N$, la lunghezza delle sequenze di DNA. Le tre righe successive contengono stringhe binarie di lunghezza $N$ che rappresentano le sequenze di DNA di nani, gnomi e bronzeling.

Output

Per ogni caso di test, stampa un singolo intero $x$ tale che la lunghezza della più lunga sottosequenza comune delle tre sequenze di DNA cada nell'intervallo $[x, 2x]$.

Limiti

$1 \le T \le 10$, $1 \le N \le 3000$, ogni stringa è composta solo dalle cifre 0 e 1.

Esempi

Input 1

2
4
0010
0110
0101
2
10
00
01

Output 1

2
1

Note

Nel primo esempio, la LCS ottimale è 010, quindi la sua lunghezza è $3$. Pertanto anche la risposta $2$ è corretta.