Arkitektur är ofta resultatet av friktion mellan två briljanta men motsatta sinnen. Kotori och Umi, chefsarkitekter för en ny storstadspromenad, har hamnat i ett dödläge kring stenläggningens estetiska riktning. Promenaden modelleras som en sekvens av $n$ rutor på en enda rad.

Vissa rutor har redan stenlagts: en del innehåller Kotoris signatur av vit marmor, medan andra innehåller Umis föredragna svarta granit. Många rutor är fortfarande tomma (markerade som "?"). Kotori och Umi måste nu fylla de återstående rutorna en efter en.

För att säkerställa total rättvisa i samarbetet och förhindra att en enskild filosofi dominerar utan kamp, har de enats om ett formellt designprotokoll:

• Kotori och Umi turas om att placera en enskild sten i en tom ruta, där Kotori börjar.
• Kotori placerar alltid en vit marmorsten, eftersom hon anser att promenadens skönhet mäts av dess längsta sammanhängande segment av vit marmor. Hon försöker naturligtvis maximera denna längd.
• Umi, som vill skapa strukturell kontrast och rytm, anser att långa, oavbrutna vita segment är monotona. Hon placerar alltid en svart granitsten i syfte att minimera samma maximala längd.

När en sten väl har placerats kan den varken flyttas eller bytas ut. Processen fortsätter tills alla tomma rutor är fyllda.

Givet promenadens starttillstånd är din uppgift att bestämma den slutliga "Estetiska poängen" — längden på det längsta sammanhängande segmentet av vit marmor — under antagandet att båda arkitekterna spelar optimalt för att uppnå sina respektive estetiska mål.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^4$) som anger antalet testfall. För varje testfall:

Den första och enda raden innehåller en enda sträng $s_1 s_2 \dots s_n$ med längden $n$ ($1 \le n \le 10^5$), där:

• 0 representerar en ruta som redan innehåller Kotoris vita marmor;
• 1 representerar en ruta som redan innehåller Umis svarta granit;
• ? representerar en för närvarande tom ruta.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett heltal som anger spelets slutpoäng.

Exempel

Indata 1

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

Utdata 1

1
3
0
3
5
5