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이다. 같으면 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$에 대해 $f(s)$는 $s$를 이진수로 해석한 값이다. 예를 들어 $s = 11010$이면 $f(s) = 26$이다.

$g(s_1, s_2)$는 $f(s_1)$과 $f(s_2)$의 배타적 논리합이다. $S$의 부분문자열 $s_1$, $s_2$를 골라 만들 수 있는 $g(s_1, s_2)$의 최댓값을 구하라.

$s_1$과 $s_2$가 서로 달라야 하는 것은 아니다. $S$에서 일부가 겹쳐도 되고, 완전히 같은 부분문자열이어도 된다.

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

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

각 테스트 케이스마다 $g(s_1, s_2)$의 최댓값을 이진법으로 한 줄에 출력한다. 불필요한 앞자리 0은 출력하지 않는다.

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