이 문제의 비정상적인 시간 제한에 유의하세요.

생물학자 드워프는 최근 브로츠와프 대학교의 민속 유전학 분야에서 획기적인 발견을 해냈습니다. 수년간의 연구 끝에 그는 도시에 서식하는 세 가지 서로 다른 종족인 드워프(자신의 종족), 노움(마법 숲의 거주자), 그리고 브론즐링(브로츠와프 거리의 전설적인 청동 조각상 일족)의 DNA 염기서열을 분석하는 데 성공했습니다.

각 DNA 서열은 이진 문자열로 표현되며, 여기서 0은 열성 유전 표지자를 나타내고 1은 우성 유전 표지자를 나타냅니다. 그의 목표는 세 종족이 모두 공유하는 유전 표지자의 최장 공통 부분 수열(LCS)을 찾는 것입니다. 이는 그들의 공통 진화 조상을 밝혀내고 왜 그들 모두가 브로츠와프에 정착하게 되었는지를 설명해 줄 것입니다! 그러나 세 서열의 정확한 LCS를 계산하는 것은 계산 비용이 많이 들고, 드워프의 연구 지원금은 바닥나고 있습니다. 그에게는 완벽한 정확도가 필요하지 않으며, 실제 3-LCS의 길이가 구간 $[x, 2x]$에 속하는 정수 $x$를 찾기만 하면 됩니다. 다시 말해, $2$-근사치면 충분합니다.

이 근사치는 그의 연구 논문에 충분히 훌륭한 자료가 될 것이며 브로츠와프의 마법 주민들이 공유하는 유전적 유산에 대한 귀중한 통찰을 여전히 제공할 것입니다. 드워프가 그러한 근사치를 찾을 수 있도록 도와주겠습니까?

입력

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 숫자 $T$가 주어집니다.

각 테스트 케이스는 네 줄로 구성됩니다. 첫 번째 줄에는 DNA 서열의 길이를 나타내는 정수 $N$이 주어집니다. 다음 세 줄에는 드워프, 노움, 브론즐링의 DNA 서열을 나타내는 길이 $N$의 이진 문자열이 주어집니다.

출력

각 테스트 케이스마다 세 DNA 서열의 최장 공통 부분 수열의 길이가 구간 $[x, 2x]$에 속하도록 하는 하나의 정수 $x$를 출력합니다.

제한

$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$도 정답입니다.