Lưu ý giới hạn thời gian khác thường trong bài toán này.

Chú lùn Nhà sinh vật học gần đây đã tạo ra một khám phá đột phá trong lĩnh vực di truyền học dân gian tại Đại học Wrocław. Sau nhiều năm nghiên cứu, ông đã giải trình tự thành công DNA của ba loài khác nhau sinh sống trong thành phố: người lùn (giống loài của chính ông), thần rừng gnome (những cư dân khu rừng phép thuật), và người đồng bronzeling (tộc tượng đồng huyền thoại trên đường phố Wrocław).

Mỗi trình tự DNA được biểu diễn dưới dạng một xâu nhị phân, trong đó 0 biểu thị một dấu ấn di truyền lặn và 1 biểu thị một dấu ấn di truyền trội. Mục tiêu của ông là tìm dãy con chung dài nhất (LCS) của các dấu ấn di truyền được chia sẻ giữa cả ba loài — điều này sẽ tiết lộ tổ tiên tiến hóa chung của họ và giải thích tại sao tất cả họ lại cùng xuất hiện ở Wrocław! Tuy nhiên, việc tính toán chính xác LCS của ba dãy rất tốn kém về mặt tính toán, và quỹ tài trợ nghiên cứu của chú lùn đang dần cạn kiệt. Ông không cần độ chính xác tuyệt đối; ông chỉ cần tìm một số nguyên $x$ sao cho độ dài thực sự của 3-LCS nằm trong đoạn $[x, 2x]$. Nói cách khác, một xấp xỉ hệ số $2$ là đủ.

Sự xấp xỉ này sẽ đủ tốt cho bài báo nghiên cứu của ông và vẫn cung cấp những hiểu biết có giá trị về di sản di truyền chung của các cư dân phép thuật tại Wrocław. Bạn có thể giúp chú lùn tìm một xấp xỉ như vậy không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số $T$, biểu thị số lượng bộ test.

Mỗi bộ test gồm bốn dòng. Dòng đầu tiên chứa một số nguyên $N$, độ dài của các trình tự DNA. Ba dòng tiếp theo chứa các xâu nhị phân độ dài $N$ biểu thị các trình tự DNA của người lùn, thần rừng gnome và người đồng bronzeling.

Kết quả

Với mỗi bộ test, hãy in ra một số nguyên duy nhất $x$ sao cho độ dài của dãy con chung dài nhất của ba trình tự DNA nằm trong đoạn $[x, 2x]$.

Giới hạn

$1 \le T \le 10$, $1 \le N \le 3000$, mỗi xâu chỉ bao gồm các chữ số 0 và 1.

Ví dụ

Dữ liệu vào 1

2
4
0010
0110
0101
2
10
00
01

Kết quả 1

2
1

Giải thích

Trong ví dụ đầu tiên, LCS tối ưu là 010, nên độ dài của nó là $3$. Do đó câu trả lời $2$ cũng là chính xác.