غالباً ما تكون الهندسة المعمارية نتاج احتكاك بين عقلين بارعين ولكنهما متضادان. تجد كوتوري (Kotori) وأومي (Umi)، المهندستان الرئيسيتان لممشى حضري جديد، نفسيهما في طريق مسدود بشأن التوجه الجمالي لرصف الممشى. يتم تمثيل الممشى كمتتالية من $n$ خلايا في صف واحد.

تم رصف بعض الخلايا بالفعل: يحتوي بعضها على الرخام الأبيض المميز لكوتوري، بينما يحتوي البعض الآخر على الجرانيت الأسود المفضل لدى أومي. لا تزال العديد من الخلايا فارغة (مشار إليها بالرمز "?"). يجب على كوتوري وأومي الآن ملء الخلايا المتبقية واحدة تلو الأخرى.

لضمان العدالة التامة في تعاونهما ومنع أي فلسفة منفردة من الهيمنة دون منافسة، اتفقتا على بروتوكول تصميم رسمي:

• تتناوب كوتوري وأومي على وضع حجر واحد في خلية فارغة، على أن تبدأ كوتوري أولاً.
• تضع كوتوري دائماً حجراً من الرخام الأبيض، لأنها تعتقد أن جمال الممشى يُقاس بطول أطول مقطع متجاور من الرخام الأبيض. وهي تسعى بطبيعة الحال إلى تعظيم هذا الطول.
• تسعى أومي إلى توفير تباين هيكلي وإيقاع، وتعتقد أن المقاطع البيضاء الطويلة غير المنقطعة رتيبة. لذلك تضع دائماً حجراً من الجرانيت الأسود، بهدف تقليل ذلك الطول الأقصى نفسه.

بمجرد وضع الحجر، لا يمكن نقله أو استبداله. وتستمر العملية حتى يتم ملء جميع الخلايا الفارغة.

بالنظر إلى الحالة الأولية للممشى، فإن مهمتك هي تحديد "النتيجة الجمالية" النهائية — أي طول أطول مقطع متجاور من الرخام الأبيض — بافتراض أن كلتا المهندستين تلعبان بشكل أمثل لتحقيق أهدافهما الجمالية الخاصة.

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 10^4$) يشير إلى عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول والوحيد على سلسلة نصية واحدة $s_1 s_2 \dots s_n$ بطول $n$ ($1 \le n \le 10^5$)، حيث:

• 0 يمثل خلية تحتوي بالفعل على رخام كوتوري الأبيض؛
• 1 يمثل خلية تحتوي بالفعل على جرانيت أومي الأسود؛
• ? يمثل خلية فارغة حالياً.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $10^6$.

الإخراج

لكل حالة اختبار، اطبع سطراً واحداً يحتوي على عدد صحيح يشير إلى النتيجة النهائية للعبة.

أمثلة

الإدخال 1

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

الإخراج 1

1
3
0
3
5
5