Arkkitehtuuri on usein tulosta kahden loistavan mutta vastakkaisen ajattelijan välisestä kitkasta. Uuden suurkaupungin rantabulevardin pääarkkitehdit Kotori ja Umi ovat ajautuneet umpikujaan kiveyksen esteettisestä suunnasta. Bulevardi mallinnetaan yhdessä rivissä olevana $n$ ruudun jonona.

Osa ruuduista on jo kivetty: joissakin on Kotorin tavaramerkiksi muodostunutta valkoista marmoria, kun taas toisissa on Umin suosimaa mustaa graniittia. Monet ruudut ovat vielä tyhjiä (merkitty merkillä ”?”). Kotorin ja Umin täytyy nyt täyttää jäljellä olevat ruudut yksi kerrallaan.

Varmistaakseen täydellisen oikeudenmukaisuuden yhteistyössään ja estääkseen yhtä ainoaa filosofiaa hallitsemasta ilman kamppailua he ovat sopineet muodollisesta suunnittelukäytännöstä:

• Kotori ja Umi asettavat vuorotellen yhden kiven tyhjään ruutuun, ja Kotori aloittaa.
• Kotori asettaa aina valkoisen marmorikiven, sillä hän uskoo bulevardin kauneuden määräytyvän valkoisten marmorien pisimmän yhtenäisen jakson pituuden mukaan. Hän pyrkii luonnollisesti maksimoimaan tämän pituuden.
• Rakenteellista kontrastia ja rytmiä tavoitteleva Umi uskoo, että pitkät, katkeamattomat valkoiset jaksot ovat yksitoikkoisia. Hän asettaa aina mustan graniittikiven pyrkien minimoimaan tuon saman maksimipituuden.

Kun kivi on asetettu, sitä ei voi siirtää eikä vaihtaa. Prosessi jatkuu, kunnes kaikki tyhjät ruudut on täytetty.

Tehtäväsi on määrittää bulevardin alkutilanteen perusteella lopullinen ”Esteettinen pistemäärä” — valkoisten marmorien pisimmän yhtenäisen jakson pituus — olettaen, että molemmat arkkitehdit pelaavat optimaalisesti saavuttaakseen omat esteettiset tavoitteensa.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen ja ainoa rivi sisältää yhden merkkijonon $s_1 s_2 \dots s_n$, jonka pituus on $n$ ($1 \le n \le 10^5$), missä:

• 0 tarkoittaa ruutua, jossa on jo Kotorin valkoista marmoria;
• 1 tarkoittaa ruutua, jossa on jo Umin mustaa graniittia;
• ? tarkoittaa tällä hetkellä tyhjää ruutua.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaisesta testitapauksesta yksi rivi, joka sisältää pelin lopullisen pistemäärän ilmaisevan kokonaisluvun.

Esimerkit

Syöte 1

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

Tuloste 1

1
3
0
3
5
5