אדריכלות היא לעיתים קרובות תוצאה של חיכוך בין שני מוחות מבריקים אך מנוגדים. קוטורי (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