Notez la limite de temps inhabituelle dans cette tâche.

Le Nain Biologiste a récemment fait une découverte révolutionnaire dans le domaine de la génétique folklorique à l'Université de Wrocław. Après des années de recherche, il a réussi à séquencer l'ADN de trois espèces distinctes qui habitent la ville : les nains (sa propre espèce), les gnomes (les habitants de la forêt magique) et les bronzelings (le peuple légendaire des statues de bronze des rues de Wrocław).

Chaque séquence d'ADN est représentée par une chaîne binaire, où 0 désigne un marqueur génétique récessif et 1 désigne un marqueur dominant. Son objectif est de trouver la plus longue sous-séquence commune (LCS) de marqueurs génétiques partagés par les trois espèces — cela révélerait leur ancêtre évolutif commun et expliquerait pourquoi ils se sont tous retrouvés à Wrocław ! Cependant, le calcul de la LCS exacte de trois séquences est coûteux en calcul, et la bourse de recherche du nain touche à sa fin. Il n'a pas besoin d'une précision parfaite ; il a juste besoin de trouver un entier $x$ tel que la véritable longueur de la 3-LCS se situe dans l'intervalle $[x, 2x]$. En d'autres termes, une $2$-approximation suffira.

Cette approximation sera suffisamment bonne pour son article de recherche et fournira toujours des informations précieuses sur l'héritage génétique partagé des habitants magiques de Wrocław. Pouvez-vous aider le nain à trouver une telle approximation ?

Entrée

La première ligne de l'entrée contient le nombre $T$, représentant le nombre de cas de test.

Chaque cas de test se compose de quatre lignes. La première ligne contient un entier $N$, la longueur des séquences d'ADN. Les trois lignes suivantes contiennent des chaînes binaires de longueur $N$ représentant les séquences d'ADN des nains, des gnomes et des bronzelings.

Sortie

Pour chaque cas de test, affichez un seul entier $x$ tel que la longueur de la plus longue sous-séquence commune des trois séquences d'ADN se situe dans l'intervalle $[x, 2x]$.

Contraintes

$1 \le T \le 10$, $1 \le N \le 3000$, chaque chaîne est composée uniquement des chiffres 0 et 1.

Exemples

Entrée 1

2
4
0010
0110
0101
2
10
00
01

Sortie 1

2
1

Note

Dans le premier exemple, la LCS optimale est 010, sa longueur est donc $3$. Par conséquent, la réponse $2$ est également correcte.