ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 I: cats 的电脑中毒

内存限制：512 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：2 通过：1
返回比赛提交提交记录

题目描述

cats 的电脑被电脑病毒感染了。cats的电脑可视为所有 2 n 个长度为 n 的，只包含 0, 1 两种字符的字符 串的集合。每一个字符串为一个节点。如果两个节点的字符串之间有且仅有一个位置的字符不同，则认 为这两个节点是相邻的。例如节点 1111 和节点 1110 是相邻的，但节点 101 和节点 000 不是相邻的。

在第 0 秒时，电脑病毒感染了三个节点 S1, S2, S3。从第 1 秒开始，每一秒每个被电脑病毒感染的节点 都会感染与它相邻的所有未被感染的节点。当所有节点都被感染时，cats 的电脑就损坏了。现在，你需 要求出 cats 的电脑损坏的时间（按秒计算）. 


				

			

		

	



    

  

      

      

          
输入格式

          

	第一行包含一个整数 T (1 ≤ T ≤ 10^4
)，表示一共有 T 组测试数据。



	 每组测试数据的第一行为一个整数 n (2 ≤ n ≤ 2 · 10^5
)，表示 cats 的电脑的节点的字符串长度。



	 接下来 3 行，每行包含一个长为 n 的，只包含 0, 1 两种字符的字符串 Si，表示初始被电脑病毒感染的
节点。



	保证对于任意的 1 ≤ i < j ≤ 3，Si 与 Sj 不完全相同。 



	保证所有测试数据的 n 之和不超过 10^6。


      

    

        

        

          
输出格式

          
对于每组测试数据，输出一个整数，表示 cats 的电脑损坏的时间（按秒计算）。

        

    

  
        

        

          
输入样例
          复制
          

          
          

            
            
4
2
01
10
11
3
011
000
110
7
1011001
0101110
0110100
10
0110110100
1100100010
0001110111


          

        

    

        

        

          
输出样例
          复制
          

          
          

            
              
1
2
4
7

            
          

        

    

  
  
          

      

        

        分类标签