L'architecture est souvent le fruit de la friction entre deux esprits brillants mais opposés. Kotori et Umi, architectes en chef d'une nouvelle promenade métropolitaine, se retrouvent dans une impasse concernant l'orientation esthétique du pavage. La promenade est modélisée comme une séquence de $n$ cases sur une seule rangée.

Certaines cases ont déjà été pavées : certaines contiennent le marbre blanc emblématique de Kotori, tandis que d'autres contiennent le granit noir préféré d'Umi. De nombreuses cases restent vides (marquées par « ? »). Kotori et Umi doivent maintenant remplir les cases restantes une par une.

Pour garantir une équité totale dans leur collaboration et empêcher qu'une seule philosophie ne domine sans lutte, elles ont convenu d'un protocole de conception formel :

• Kotori et Umi placent à tour de rôle une seule pierre dans une case vide, Kotori commençant en premier.
• Kotori place toujours une pierre de marbre blanc, car elle estime que la beauté de la promenade se mesure à son plus long segment contigu de marbres blancs. Elle cherche naturellement à maximiser cette longueur.
• Umi, cherchant à apporter un contraste structurel et du rythme, estime que les longs segments blancs ininterrompus sont monotones. Elle place toujours une pierre de granit noir, dans le but de minimiser cette même longueur maximale.

Une fois qu'une pierre est placée, elle ne peut être ni déplacée ni remplacée. Le processus se poursuit jusqu'à ce que toutes les cases vides soient remplies.

Étant donné l'état initial de la promenade, votre tâche consiste à déterminer le « Score Esthétique » final — la longueur du plus long segment contigu de marbres blancs — en supposant que les deux architectes jouent de manière optimale pour atteindre leurs objectifs esthétiques respectifs.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première et unique ligne contient une seule chaîne de caractères $s_1 s_2 \dots s_n$ de longueur $n$ ($1 \le n \le 10^5$), où :

• 0 représente une case contenant déjà le marbre blanc de Kotori ;
• 1 représente une case contenant déjà le granit noir d'Umi ;
• ? représente une case actuellement vide.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un entier indiquant le score final du jeu.

Exemples

Entrée 1

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

Sortie 1

1
3
0
3
5
5