Ten en cuenta el límite de tiempo inusual en esta tarea.

El Enano Biólogo ha hecho recientemente un descubrimiento revolucionario en el campo de la genética folclórica en la Universidad de Breslavia (Wrocław). Tras años de investigación, ha logrado secuenciar con éxito el ADN de tres especies distintas que habitan la ciudad: enanos (su propia especie), gnomos (los habitantes del bosque mágico) y bronzelings (la legendaria gente estatua de bronce de las calles de Breslavia).

Cada secuencia de ADN se representa como una cadena binaria, donde 0 denota un marcador genético recesivo y 1 denota uno dominante. Su objetivo es encontrar la subsecuencia común más larga (LCS) de marcadores genéticos compartidos entre las tres especies — ¡esto revelaría su ancestro evolutivo común y explicaría por qué todos terminaron en Breslavia! Sin embargo, calcular la LCS exacta de tres secuencias es computacionalmente costoso, y la beca de investigación del enano se está agotando. No necesita una precisión perfecta; solo necesita encontrar un entero $x$ tal que la longitud real de la 3-LCS se encuentre en el intervalo $[x, 2x]$. En otras palabras, una $2$-aproximación será suficiente.

Esta aproximación será lo suficientemente buena para su artículo de investigación y seguirá proporcionando información valiosa sobre la herencia genética compartida de los habitantes mágicos de Breslavia. ¿Puedes ayudar al enano a encontrar dicha aproximación?

Entrada

La primera línea de la entrada contiene el número $T$, que representa el número de casos de prueba.

Cada caso de prueba consta de cuatro líneas. La primera línea contiene un entero $N$, la longitud de las secuencias de ADN. Las siguientes tres líneas contienen cadenas binarias de longitud $N$ que representan las secuencias de ADN de los enanos, gnomos y bronzelings.

Salida

Para cada caso de prueba, imprime un solo entero $x$ tal que la longitud de la subsecuencia común más larga de las tres secuencias de ADN se encuentre en el intervalo $[x, 2x]$.

Límites

$1 \le T \le 10$, $1 \le N \le 3000$, cada cadena consta únicamente de los dígitos 0 y 1.

Ejemplos

Entrada 1

2
4
0010
0110
0101
2
10
00
01

Salida 1

2
1

Nota

En el primer ejemplo, la LCS óptima es 010, por lo que su longitud es $3$. Por lo tanto, la respuesta $2$ también es correcta.