Зверніть увагу на незвичне обмеження за часом у цій задачі.

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

Кожна послідовність ДНК подається у вигляді бінарного рядка, де 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$ також є правильною.