下午茶大作战
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

「轻音部永远不会完结！」
「毕业！？」
『轻音少女永不毕业！』
这是《轻音少女》的一条新的世界线！

田井中律打算在樱丘高中成立轻音部，但是由于樱丘高中规定社团的成立至少要有4名成员，即使田井中律拉上了秋山澪和琴吹䌷，也因轻音部不足4人面临废部的风险。

但是在这个时间线中，呆呆的平泽唯误打误撞来到了音乐室，为了能够将平泽唯留下来，轻音部的大家一致决定开展下午茶大作战。


最后的废部期限还有 n 天就要到来了，轻音部的3个人 希望在此期间尽可能多的给喜欢甜食的平泽唯提供下午茶。

为此，我们将轻音部3位部员接下来 n 的空闲情况，分别记为三组 01 串 \{a_{i}\},\{b_{i}\} 和 \{c_{i}\}。若 a_{i}=1，则表示田井中律在第 i 天是空闲的，可以参与下午茶；若 a_{i}=0，则表示田井中律在第 i 天已经有了别的安排，不可以参与下午茶。类似的，b_{i} 和 c_{i} 也分别表示了秋山澪和琴吹䌷在第 i 天的空闲情况。

由于种种不可描述的原因，如果某一天 轻音部 打算进行举办下午茶，就必须同时有2名部员参与，且不能连续两天的参加的两人完全相同，否则 轻音部 在当天就不能举办下午茶。我们想知道，在此基础上，轻音部可以举办下午茶的最多天数是多少？

输入描述:

本题每组输入包含多组测试用例！

输入的第一行包含一行一个正整数 T(1\le T\le10^{4})，测试用例数。

对于每组测试用例：
- 输入的第一行包含一个正整数 n(1\le n\le10^{5})，表示距离下一次重测的天数。
- 接下来输出一行一个长度为n 的 01 串 ，表示田井中律在接下来 n 天内的空闲情况。
- 接下来输出一行一个长度为 n 的 01 串 \{b_{i}\}，表示秋山澪在接下来 n 天内的空闲情况。
- 接下来输出一行一个长度为 n 的 01 串\{c_{i}\}，表示琴吹䌷在接下来 n 天内的空闲情况。

输入数据保证各组测试用例中 n 的值的总和不超过 5\times10^{5}。

输出描述:

对于每组测试用例，输出一行一个正整数，表示满足题目要求下可以举办下午茶的最多天数。
示例1

输入

复制 
5
6
101010
111111
010101
6
111111
111111
000000
6
101110
010111
111101
6
010010
101001
000110
6
010010
101001
000000

输出

复制 
6
3
6
1
0