Arkitektur er ofte resultatet av friksjon mellom to briljante, men motstridende sinn. Kotori og Umi, sjefsarkitekter for en ny storby-promenade, har havnet i en fastlåst situasjon angående broleggingens estetiske retning. Promenaden modelleres som en sekvens av $n$ ruter på én enkelt rad.

Noen ruter er allerede brolagt: noen inneholder Kotoris signatur av hvit marmor, mens andre inneholder Umis foretrukne svarte granitt. Mange ruter står fortsatt tomme (markert som «?»). Kotori og Umi må nå fylle de gjenværende rutene én etter én.

For å sikre fullstendig rettferdighet i samarbeidet og forhindre at én enkelt filosofi dominerer uten kamp, har de blitt enige om en formell designprotokoll:

• Kotori og Umi bytter på å plassere én enkelt stein i en tom rute, og Kotori starter.
• Kotori plasserer alltid en hvit marmorstein, siden hun mener at promenadens skjønnhet måles ved dens lengste sammenhengende segment av hvit marmor. Hun forsøker naturligvis å maksimere denne lengden.
• Umi, som ønsker å skape strukturell kontrast og rytme, mener at lange, uavbrutte hvite segmenter er monotone. Hun plasserer alltid en svart granittstein, med mål om å minimere den samme maksimale lengden.

Når en stein først er plassert, kan den ikke flyttes eller byttes ut. Prosessen fortsetter til alle tomme ruter er fylt.

Gitt promenadens starttilstand er din oppgave å bestemme den endelige «Estetiske poengsummen» — lengden på det lengste sammenhengende segmentet av hvit marmor — under forutsetning av at begge arkitektene spiller optimalt for å nå sine respektive estetiske mål.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$) som angir antall testtilfeller. For hvert testtilfelle:

Den første og eneste linjen inneholder én enkelt streng $s_1 s_2 \dots s_n$ med lengde $n$ ($1 \le n \le 10^5$), der:

• 0 representerer en rute som allerede inneholder Kotoris hvite marmor;
• 1 representerer en rute som allerede inneholder Umis svarte granitt;
• ? representerer en rute som for øyeblikket er tom.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder et heltall som angir den endelige poengsummen i spillet.

Eksempler

Inndata 1

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

Utdata 1

1
3
0
3
5
5