건축은 종종 뛰어나지만 서로 반대되는 생각을 가진 두 지성의 마찰을 통해 탄생합니다. 새로운 대도시 산책로의 수석 건축가인 코토리(Kotori)와 우미(Umi)는 보도블록의 미학적 방향을 두고 교착 상태에 빠졌습니다. 산책로는 한 줄로 늘어선 $n$개의 칸으로 모델링됩니다.

일부 칸은 이미 포장되어 있습니다. 어떤 칸에는 코토리의 시그니처인 흰색 대리석이 깔려 있고, 다른 칸에는 우미가 선호하는 검은색 화강암이 깔려 있습니다. 많은 칸은 여전히 비어 있습니다("?"로 표시됨). 이제 코토리와 우미는 남은 칸들을 하나씩 채워야 합니다.

협력의 완전한 공정성을 보장하고 어느 한쪽의 철학이 경쟁 없이 지배하는 것을 방지하기 위해, 두 사람은 공식적인 설계 프로토콜에 합의했습니다:

• 코토리와 우미는 코토리부터 시작하여 번갈아 가며 빈칸 하나에 돌 하나를 놓습니다.
• 코토리는 산책로의 아름다움이 흰색 대리석의 가장 긴 연속 구간의 길이로 측정된다고 믿기 때문에 항상 흰색 대리석을 놓습니다. 그녀는 당연히 이 길이를 최대화하려고 합니다.
• 구조적 대비와 리듬감을 추구하는 우미는 길고 끊기지 않는 흰색 구간이 단조롭다고 생각합니다. 그녀는 항상 검은색 화강암을 놓으며, 그 동일한 최대 길이를 최소화하는 것을 목표로 합니다.

한 번 놓인 돌은 옮기거나 바꿀 수 없습니다. 이 과정은 모든 빈칸이 채워질 때까지 계속됩니다.

산책로의 초기 상태가 주어졌을 때, 두 건축가가 각자의 미학적 목표를 달성하기 위해 최적으로 플레이한다고 가정하고 최종 "미학적 점수" — 흰색 대리석의 가장 긴 연속 구간의 길이 — 를 구하는 것이 여러분의 작업입니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 각 테스트 케이스에 대해:

유일한 줄에 길이 $n$ ($1 \le n \le 10^5$)인 단일 문자열 $s_1 s_2 \dots s_n$이 주어지며, 여기서:

• 0은 이미 코토리의 흰색 대리석이 들어 있는 칸을 나타내고,
• 1은 이미 우미의 검은색 화강암이 들어 있는 칸을 나타내며,
• ?는 현재 비어 있는 칸을 나타냅니다.

모든 테스트 케이스에서 $n$의 합은 $10^6$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 게임의 최종 점수를 나타내는 정수를 한 줄에 하나씩 출력합니다.

예제

입력 1

6
??
000
111
0??0??0
0?0?0?0
00?00?100?0

출력 1

1
3
0
3
5
5