Architektur ist oft das Ergebnis von Reibung zwischen zwei brillanten, aber gegensätzlichen Köpfen. Kotori und Umi, die leitenden Architektinnen für eine neue Großstadtpromenade, befinden sich in einer Pattsituation bezüglich der ästhetischen Ausrichtung der Pflasterung. Die Promenade wird als eine Folge von $n$ Feldern in einer einzigen Reihe modelliert.

Einige Felder wurden bereits gepflastert: Einige enthalten Kotoris charakteristischen weißen Marmor, während andere Umis bevorzugten schwarzen Granit enthalten. Viele Felder sind noch leer (als „?“ markiert). Kotori und Umi müssen nun die verbleibenden Felder nacheinander füllen.

Um absolute Fairness in ihrer Zusammenarbeit zu gewährleisten und zu verhindern, dass eine einzelne Philosophie kampflos dominiert, haben sie sich auf ein formelles Designprotokoll geeinigt:

• Kotori und Umi legen abwechselnd einen einzelnen Stein in ein leeres Feld, wobei Kotori beginnt.
• Kotori legt immer einen weißen Marmorstein, da sie glaubt, dass die Schönheit der Promenade an ihrem längsten zusammenhängenden Abschnitt aus weißem Marmor gemessen wird. Sie versucht natürlich, diese Länge zu maximieren.
• Umi, die für strukturellen Kontrast und Rhythmus sorgen möchte, hält lange, ununterbrochene weiße Abschnitte für monoton. Sie legt immer einen schwarzen Granitstein mit dem Ziel, genau diese maximale Länge zu minimieren.

Sobald ein Stein gelegt wurde, kann er weder verschoben noch ersetzt werden. Der Vorgang wird fortgesetzt, bis alle leeren Felder gefüllt sind.

Ihre Aufgabe ist es, ausgehend vom Anfangszustand der Promenade die endgültige „Ästhetik-Wertung“ — die Länge des längsten zusammenhängenden Abschnitts aus weißem Marmor — zu bestimmen, unter der Annahme, dass beide Architektinnen optimal spielen, um ihre jeweiligen ästhetischen Ziele zu erreichen.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste und einzige Zeile enthält eine einzelne Zeichenkette $s_1 s_2 \dots s_n$ der Länge $n$ ($1 \le n \le 10^5$), wobei:

• 0 für ein Feld steht, das bereits Kotoris weißen Marmor enthält;
• 1 für ein Feld steht, das bereits Umis schwarzen Granit enthält;
• ? für ein derzeit leeres Feld steht.

Es ist garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer ganzen Zahl aus, die den Endstand des Spiels angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

1
3
0
3
5
5