60028 XOR 최대

문제

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

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

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

$0$과 $1$로만 구성된 길이가 $N$인 문자열 $S$가 주어진다.

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

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

이때 $s_1$과 $s_2$가 서로 다를 필요는 없다. 즉, $s_1$과 $s_2$는 $S$에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.

$0$과 $1$로만 구성된 문자열 $S$가 주어지면, 가능한 $g(s_1, s_2)$의 최댓값을 구하는 프로그램을 작성하라.

입력

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

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

출력

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

제한

• 주어지는 모든 수는 정수이다.
• $1 \le T \le 100$
• $2 \le N \le 10^7$
• 모든 테스트 케이스에서 $N$의 합 $\le 10^7$
• $S$는 $0$과 $1$로만 이루어진 길이가 $N$인 문자열이다.

서브태스크

1	17	$N \le 30$, 모든 테스트 케이스에서 $N$의 합 $\le 300$
2	20	$N \le 200$, 모든 테스트 케이스에서 $N$의 합 $\le 2000$
3	13	$N \le 3\,000$, 모든 테스트 케이스에서 $N$의 합 $\le 30\,000$
4	12	$N \le 2 \times 10^5$, 모든 테스트 케이스에서 $N$의 합 $\le 2 \times 10^6$
5	38	추가 제약 조건 없음.

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