لاحظ الحد الزمني غير المعتاد في هذه المسألة.

حقق القزم عالم الأحياء مؤخراً اكتشافاً رائداً في مجال علم الوراثة الفولكلوري في جامعة فروتسواف. بعد سنوات من البحث، نجح في تحديد تسلسل الحمض النووي (DNA) لثلاثة أنواع متميزة تسكن المدينة: الأقزام (بني جنسه)، والجنوم (سكان الغابة السحرية)، والبرونزيين (شعب التماثيل البرونزية الأسطوري في شوارع فروتسواف).

يتم تمثيل كل تسلسل حمض نووي كسلسلة ثنائية، حيث يرمز 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$ صحيحة أيضاً.