자연수 스트리머

0과 1로만 이루어진 길이 $N$의 이진 문자열 $S$가 주어진다. 어떤 자연수 $x$의 0으로 시작하지 않는 이진수 표현을 $\mathrm{bin}(x)$라고 하자. 이 문제에서 자연수는 $0$을 포함하며, 예외적으로 $\mathrm{bin}(0) =$ 0이다.

문자열 $T$의 점수란, 어떤 두 자연수 $0\leq l\leq r$에 대해 $T$가 $\mathrm{bin}(l)$, $\mathrm{bin}(l+1)$, $\cdots$, $\mathrm{bin}(r)$을 이어붙여 쓴 문자열과 일치할 때, 그러한 $(l,r)$ 쌍 중 $(r-l+1)$의 최댓값이다. 그러한 $(l,r)$이 존재하지 않으면 $T$의 점수는 $0$점이다.

$S$의 부분 문자열(substring) 중 점수가 가장 높은 것의 점수를 구하라. 문자열의 부분 문자열이란, 그 문자열의 앞과 뒤에서 몇 글자씩 지워서 만들 수 있는 문자열이다(아무것도 지우지 않아도 된다).

첫째 줄에 테스트 케이스의 개수 $1\leq T\leq 500\,000$이 주어진다.

각 테스트 케이스마다, 첫째 줄에 이진 문자열의 길이 $1\leq N\leq 500\,000$이 주어진다. 그다음 줄에 0과 1로만 구성된 길이 $N$의 문자열 $S$가 주어진다.

모든 테스트 케이스에서 $N$의 합은 $500\,000$을 넘지 않는다.

각 테스트 케이스마다 답을 한 줄에 하나씩, 총 $T$개의 줄에 걸쳐 출력한다.