โปรดสังเกตขีดจำกัดเวลาที่ไม่ปกติในโจทย์ข้อนี้

คนแคระนักชีววิทยาเพิ่งทำการค้นพบครั้งสำคัญในสาขาพันธุศาสตร์พื้นบ้านที่มหาวิทยาลัยวรอตสวัฟ หลังจากวิจัยมานานหลายปี เขาก็ประสบความสำเร็จในการจัดลำดับ DNA ของสิ่งมีชีวิตสามสายพันธุ์ที่แตกต่างกันซึ่งอาศัยอยู่ในเมือง ได้แก่ คนแคระ (เผ่าพันธุ์ของเขาเอง), โนม (ผู้อาศัยในป่าเวทมนตร์) และบรอนซ์ลิง (ชาวรูปปั้นสัมฤทธิ์ในตำนานแห่งท้องถนนของวรอตสวัฟ)

ลำดับ DNA แต่ละสายจะถูกแทนด้วยสตริงฐานสอง โดยที่ 0 แทนเครื่องหมายทางพันธุกรรมแบบด้อย และ 1 แทนเครื่องหมายทางพันธุกรรมแบบเด่น เป้าหมายของเขาคือการหาลำดับย่อยร่วมที่ยาวที่สุด (LCS) ของเครื่องหมายทางพันธุกรรมที่มีร่วมกันในทั้งสามสายพันธุ์ ซึ่งจะเผยให้เห็นบรรพบุรุษทางวิวัฒนาการร่วมกันของพวกเขา และอธิบายว่าทำไมพวกเขาทั้งหมดจึงมาลงเอยที่วรอตสวัฟ! อย่างไรก็ตาม การคำนวณ LCS ที่แม่นยำของสามลำดับนั้นใช้ทรัพยากรการคำนวณสูงมาก และทุนวิจัยของคนแคระกำลังจะหมดลง เขาไม่ต้องการความแม่นยำที่สมบูรณ์แบบ เขาเพียงแค่ต้องหาจำนวนเต็ม $x$ ที่ทำให้ความยาวที่แท้จริงของ 3-LCS อยู่ในช่วง $[x, 2x]$ กล่าวอีกนัยหนึ่งคือ การประมาณค่าแบบ $2$-approximation ก็เพียงพอแล้ว

การประมาณค่านี้จะดีพอสำหรับบทความวิจัยของเขา และยังคงให้ข้อมูลเชิงลึกที่มีคุณค่าเกี่ยวกับมรดกทางพันธุกรรมร่วมกันของผู้อาศัยที่มีเวทมนตร์ในวรอตสวัฟ คุณสามารถช่วยคนแคระหาค่าประมาณดังกล่าวได้หรือไม่?

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีตัวเลข $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$ จึงถูกต้องเช่นกัน