Обратите внимание на необычное ограничение по времени в этой задаче.

Гном-Биолог недавно совершил прорывное открытие в области фольклорной генетики во Вроцлавском университете. После многих лет исследований он успешно секвенировал ДНК трех различных видов, населяющих город: гномов (его собственного вида), лесных эльфов-гномов (обитателей волшебного леса) и бронзовичков (легендарного бронзового народца-статуй с улиц Вроцлава).

Каждая последовательность ДНК представляется в виде бинарной строки, где 0 обозначает рецессивный генетический маркер, а 1 — доминантный. Его цель — найти наибольшую общую подпоследовательность (LCS) генетических маркеров, общую для всех трех видов: это раскрыло бы их общее эволюционное происхождение и объяснило, почему все они оказались во Вроцлаве! Однако вычисление точной LCS трех последовательностей требует больших вычислительных затрат, а исследовательский грант гнома подходит к концу. Ему не нужна идеальная точность; ему достаточно найти такое целое число $x$, что истинная длина 3-LCS лежит в отрезке $[x, 2x]$. Иными словами, подойдет $2$-аппроксимация.

Такого приближения будет вполне достаточно для его научной статьи, и оно все равно даст ценное представление об общем генетическом наследии волшебных обитателей Вроцлава. Сможете ли вы помочь гному найти такое приближение?

Входные данные

Первая строка входных данных содержит число $T$, обозначающее количество наборов входных данных.

Каждый набор входных данных состоит из четырех строк. Первая строка содержит целое число $N$ — длину последовательностей ДНК. Следующие три строки содержат бинарные строки длины $N$, представляющие последовательности ДНК гномов, лесных гномов и бронзовичков.

Выходные данные

Для каждого набора входных данных выведите одно целое число $x$ такое, что длина наибольшей общей подпоследовательности трех последовательностей ДНК лежит в отрезке $[x, 2x]$.

Ограничения

$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$ также является правильным.