L'architettura è spesso il risultato dell'attrito tra due menti brillanti ma opposte. Kotori e Umi, architetti capo di una nuova passeggiata metropolitana, si trovano in una situazione di stallo riguardo alla direzione estetica della pavimentazione. La passeggiata è modellata come una sequenza di $n$ celle disposte su una singola riga.

Alcune celle sono già state pavimentate: alcune contengono l'iconico marmo bianco di Kotori, mentre altre contengono il granito nero preferito da Umi. Molte celle rimangono vuote (contrassegnate con "?"). Kotori e Umi devono ora riempire le celle rimanenti una alla volta.

Per garantire una totale equità nella loro collaborazione ed evitare che una singola filosofia domini senza confronto, hanno concordato un protocollo formale di progettazione:

• Kotori e Umi posizionano a turno una singola pietra in una cella vuota, con Kotori che inizia per prima.
• Kotori posiziona sempre una pietra di marmo bianco, poiché ritiene che la bellezza della passeggiata si misuri dal suo segmento contiguo più lungo di marmi bianchi. Naturalmente cerca di massimizzare questa lunghezza.
• Umi, cercando di fornire contrasto strutturale e ritmo, ritiene che lunghi segmenti bianchi ininterrotti siano monotoni. Posiziona sempre una pietra di granito nero, puntando a minimizzare quella stessa lunghezza massima.

Una volta posizionata una pietra, non può essere spostata o sostituita. Il processo continua finché tutte le celle vuote non sono state riempite.

Dato lo stato iniziale della passeggiata, il tuo compito è determinare il "Punteggio Estetico" finale — la lunghezza del segmento contiguo più lungo di marmi bianchi — supponendo che entrambi gli architetti giochino in modo ottimale per raggiungere i rispettivi obiettivi estetici.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$) che indica il numero di casi di test. Per ogni caso di test:

La prima e unica riga contiene una singola stringa $s_1 s_2 \dots s_n$ di lunghezza $n$ ($1 \le n \le 10^5$), dove:

• 0 rappresenta una cella che contiene già il marmo bianco di Kotori;
• 1 rappresenta una cella che contiene già il granito nero di Umi;
• ? rappresenta una cella attualmente vuota.

È garantito che la somma di $n$ su tutti i casi di test non supera $10^6$.

Output

Per ogni caso di test, stampa una riga contenente un intero che indica il punteggio finale del gioco.

Esempi

Input 1

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

Output 1

1
3
0
3
5
5