Architektura jest często wynikiem tarcia między dwoma genialnymi, lecz przeciwstawnymi umysłami. Kotori i Umi, główne architektki nowego wielkomiejskiego deptaka, znalazły się w impasie dotyczącym kierunku estetycznego nawierzchni. Deptak jest zamodelowany jako ciąg $n$ pól w jednym rzędzie.

Niektóre pola zostały już wybrukowane: część zawiera charakterystyczny dla Kotori biały marmur, podczas gdy inne zawierają preferowany przez Umi czarny granit. Wiele pól pozostaje pustych (oznaczonych jako „?”). Kotori i Umi muszą teraz wypełnić pozostałe pola jedno po drugim.

Aby zapewnić całkowitą uczciwość we współpracy i zapobiec zdominowaniu projektu przez jedną filozofię bez walki, uzgodniły formalny protokół projektowy:

• Kotori i Umi na zmianę umieszczają pojedynczy kamień na pustym polu, przy czym Kotori zaczyna.
• Kotori zawsze kładzie biały marmur, ponieważ uważa, że piękno deptaka mierzy się długością jego najdłuższego spójnego odcinka białych marmurów. Naturalnie dąży do maksymalizacji tej długości.
• Umi, chcąc zapewnić kontrast strukturalny i rytm, uważa, że długie, nieprzerwane białe odcinki są monotonne. Zawsze kładzie czarny granit, dążąc do minimalizacji tej samej maksymalnej długości.

Raz położonego kamienia nie można przesunąć ani wymienić. Proces trwa, dopóki wszystkie puste pola nie zostaną wypełnione.

Mając dany początkowy stan deptaka, Twoim zadaniem jest wyznaczenie końcowego „Wyniku Estetycznego” — długości najdłuższego spójnego odcinka białych marmurów — przy założeniu, że obie architektki grają optymalnie, aby osiągnąć swoje cele estetyczne.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy i jedyny wiersz zawiera pojedynczy napis $s_1 s_2 \dots s_n$ o długości $n$ ($1 \le n \le 10^5$), gdzie:

• 0 oznacza pole zawierające już biały marmur Kotori;
• 1 oznacza pole zawierające już czarny granit Umi;
• ? oznacza pole aktualnie puste.

Zagwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą końcowy wynik gry.

Przykłady

Wejście 1

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

Wyjście 1

1
3
0
3
5
5