XOR 최대

문제

어떤 문자열에서 연속한 위치에 있는 1개 이상의 문자를 선택해 순서를 유지한 채로 나열해서 얻을 수 있는 문자열을 그 문자열의 부분문자열이라 한다. 예를 들어, $001001$는 $X=1\underset{‾}{001}1X\; =\; 1\backslash underline\{001\}1$의 부분문자열이지만, $Y=10101Y\; =\; 10101$의 부분문자열은 아니다.

음이 아닌 두 정수 $A,BA,\; B$의 배타적 논리합 $A\oplus BA\; \backslash oplus\; B$는 다음과 같이 정의된다.

• 이진법으로 생각했을 때, $AA$의 $2^{k}2^k$의 자릿수와 $BB$의 $2^{k}2^k$의 자릿수가 서로 다르면 $A\oplus BA\; \backslash oplus\; B$의 $2^{k}2^k$의 자릿수가 $11$이고, 같으면 $A\oplus BA\; \backslash oplus\; B$의 $2^{k}2^k$의 자릿수가 $00$이다. (단, $k\ge 0k\; \backslash ge\; 0$)
• 예를 들어 $12\oplus 1012\; \backslash oplus\; 10$은 $12={1100}_{(2)},10={1010}_{(2)}12\; =\; 1100\_\{(2)\},\; 10\; =\; 1010\_\{(2)\}$이므로 ${1100}_{(2)}\oplus {1010}_{(2)}={0110}_{(2)}=61100\_\{(2)\}\; \backslash oplus\; 1010\_\{(2)\}\; =\; 0110\_\{(2)\}\; =\; 6$이다.

$00$과 $11$로만 구성된 길이가 $NN$인 문자열 $SS$가 주어진다.

당신은 $SS$의 부분문자열 $s_1,s_{2}s\_1,\; s\_2$를 선택해서 만들 수 있는 $g(s_1,s_2)g(s\_1,\; s\_2)$의 최댓값을 계산해야 한다. $g(s_1,s_2)g(s\_1,\; s\_2)$는 다음과 같이 정의되는 함수이다:

• $SS$의 부분문자열 $ss$에 대해, $f(s)f(s)$의 값은 $ss$를 이진법으로 해석했을 때의 값이다. 예를 들어, 만약 $s=11010s\; =\; 11010$이면 $f(s)=26f(s)\; =\; 26$이다.
• $g(s_1,s_2)g(s\_1,\; s\_2)$는 $f(s_1)f(s\_1)$과 $f(s_2)f(s\_2)$의 배타적 논리합이다.

이때 $s_{1}s\_1$과 $s_{2}s\_2$가 서로 다를 필요는 없다. 즉, $s_{1}s\_1$과 $s_{2}s\_2$는 $SS$에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.

$00$과 $11$로만 구성된 문자열 $SS$가 주어지면, 가능한 $g(s_1,s_2)g(s\_1,\; s\_2)$의 최댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수 $TT$가 주어진다.

각 테스트 케이스마다, 첫 번째 줄에 문자열의 길이 $NN$, 두 번째 줄에 $00$과 $11$로만 구성된 길이가 $NN$인 문자열 $SS$가 주어진다.

출력

각 테스트 케이스마다 가능한 $g(s_1,s_2)g(s\_1,\; s\_2)$의 최댓값을 이진법으로 한 줄에 하나씩 출력한다. 단, 정답 앞에 필요 없는 $00$은 출력하지 않는다.

4
3
010
5
10101
5
00100
5
11111

11
11111
110
11110

4
2
00
2
01
2
10
2
11

0
1
11
10