Arkitektúr er oft afleiðing núnings milli tveggja snjallra en andstæðra huga. Kotori og Umi, aðalarkitektar nýrrar göngugötu í stórborg, eru komnar í sjálfheldu varðandi fagurfræðilega stefnu hellulagnarinnar. Göngugatan er sett fram sem runa af $n$ reitum í einni röð.

Sumir reitir hafa þegar verið hellulagðir: sumir innihalda hinn einkennandi hvíta marmara sem Kotori notar, en aðrir innihalda svart granít sem Umi kýs. Margir reitir eru enn auðir (merktir sem „?“). Kotori og Umi verða nú að fylla í reitina sem eftir eru, einn í einu.

Til að tryggja algjöra sanngirni í samstarfi þeirra og koma í veg fyrir að ein hugmyndafræði ráði ríkjum átakalaust, hafa þær komið sér saman um formlega hönnunarreglu:

• Kotori og Umi skiptast á að setja einn stein í auðan reit, og Kotori byrjar.
• Kotori setur alltaf hvítan marmarastein, því hún telur að fegurð göngugötunnar mælist í lengsta samfellda búti hvítra marmarasteina. Hún leitast eðlilega við að hámarka þessa lengd.
• Umi, sem vill skapa byggingarlega andstæðu og hrynjandi, telur að langir, óslitnir hvítir bútar séu einhæfir. Hún setur alltaf svartan granítstein og stefnir að því að lágmarka þessa sömu hámarkslengd.

Þegar steinn hefur verið lagður niður er hvorki hægt að færa hann né skipta honum út. Ferlið heldur áfram þar til allir auðir reitir hafa verið fylltir.

Gefið upphafsástand göngugötunnar, þá er verkefni þitt að ákvarða endanlegt „Fagurfræðiskor“ — lengd lengsta samfellda búts hvítra marmarasteina — að því gefnu að báðir arkitektar leiki á sem bestan hátt til að ná sínum fagurfræðilegu markmiðum.

Inntak

Það eru margir prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta og eina línan inniheldur einn streng $s_1 s_2 \dots s_n$ af lengd $n$ ($1 \le n \le 10^5$), þar sem:

• 0 táknar reit sem þegar inniheldur hvítan marmara frá Kotori;
• 1 táknar reit sem þegar inniheldur svart granít frá Umi;
• ? táknar reit sem er auður eins og er.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur heiltölu sem gefur til kynna lokaskor leiksins.

Dæmi

Inntak 1

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

Úttak 1

1
3
0
3
5
5