שים לב למגבלת הזמן החריגה במשימה זו.

הגמד הביולוג עשה לאחרונה תגלית פורצת דרך בתחום הגנטיקה הפולקלורית באוניברסיטת ורוצלב. לאחר שנות מחקר, הוא הצליח לרצף את ה-DNA של שלושה מינים נפרדים המאכלסים את העיר: גמדים (בני מינו), ננסים (תושבי היער הקסום), ואנשי-ברונזה (עם פסלי הברונזה האגדי מרחובות ורוצלב).

כל רצף DNA מיוצג כמחרוזת בינארית, שבה 0 מציין סמן גנטי רצסיבי ו-1 מציין סמן דומיננטי. מטרתו היא למצוא את תת-הסדרה המשותפת הארוכה ביותר (LCS) של סמנים גנטיים המשותפים לכל שלושת המינים — דבר שיחשוף את המוצא האבולוציוני המשותף שלהם ויסביר מדוע כולם התגלגלו לוורוצלב! עם זאת, חישוב ה-LCS המדויק של ثلاث סדרות הוא יקר חישובית, ומענק המחקר של הגמד הולך ואוזל. הוא אינו זקוק לדיוק מושלם; הוא רק צריך למצוא מספר שלם $x$ כך שהאורך האמיתי של ה-3-LCS נמצא בקטע $[x, 2x]$. במילים אחרות, קירוב-$2$ יספיק בהחלט.

קירוב זה יהיה טוב מספיק עבור מאמר המחקר שלו ועדיין יספק תובנות חשובות לגבי המורשת הגנטית המשותפת של תושביה הקסומים של ורוצלב. האם תוכל לעזור לגמד למצוא קירוב כזה?

קלט

השורה הראשונה של הקלט מכילה את המספר $T$, המייצג את מספר מקרי הבדיקה.

כל מקרה בדיקה מורכב מארבע שורות. השורה הראשונה מכילה מספר שלם $N$, אורך רצפי ה-DNA. שלוש השורות הבאות מכילות מחרוזות בינאריות באורך $N$ המייצגות את רצפי ה-DNA של הגמדים, הננסים ואנשי-הברונזה.

פלט

עבור כל מקרה בדיקה, הדפס מספר שלם בודד $x$ כך שאורך תת-הסדרה המשותפת הארוכה ביותר של שלושת רצפי ה-DNA נמצא בקטע $[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$ היא נכונה.