สถาปัตยกรรมมักเป็นผลลัพธ์จากการปะทะกันทางความคิดของสองอัจฉริยะที่มีมุมมองต่างกัน Kotori และ Umi สถาปนิกหลักของทางเดินเล่นในมหานครแห่งใหม่ ตกอยู่ในภาวะชะงักงันเกี่ยวกับทิศทางความงามของการปูพื้น ทางเดินนี้ถูกจำลองเป็นลำดับของช่อง $n$ ช่องในแถวเดียว
บางช่องถูกปูพื้นไว้แล้ว: บางช่องมีหินอ่อนสีขาวอันเป็นเอกลักษณ์ของ Kotori ในขณะที่บางช่องมีหินแกรนิตสีดำที่ Umi ชื่นชอบ หลายช่องยังคงว่างเปล่า (ทำเครื่องหมายด้วย "?") ตอนนี้ Kotori และ Umi ต้องเติมช่องที่เหลือทีละช่อง
เพื่อรับประกันความยุติธรรมอย่างแท้จริงในการทำงานร่วมกัน และป้องกันไม่ให้ปรัชญาใดปรัชญาหนึ่งครอบงำโดยไม่มีการต่อสู้ พวกเขาจึงตกลงใช้เกณฑ์การออกแบบอย่างเป็นทางการ:
- Kotori และ Umi สลับกันวางหินหนึ่งก้อนลงในช่องว่าง โดย Kotori เป็นฝ่ายเริ่มก่อน
- Kotori จะวางหินอ่อนสีขาวเสมอ เพราะเธอเชื่อว่าความงามของทางเดินวัดจากความยาวของช่วงหินอ่อนสีขาวที่ติดกันยาวที่สุด โดยธรรมชาติแล้วเธอจึงพยายามทำให้ความยาวนี้มีค่ามากที่สุด
- Umi ซึ่งต้องการสร้างความตัดกันของโครงสร้างและจังหวะ เชื่อว่าช่วงสีขาวที่ยาวต่อเนื่องโดยไม่ขาดตอนนั้นน่าเบื่อ เธอจะวางหินแกรนิตสีดำเสมอ โดยมีเป้าหมายเพื่อทำให้ความยาวสูงสุดเดียวกันนั้นมีค่าน้อยที่สุด
เมื่อวางหินลงไปแล้ว จะไม่สามารถย้ายหรือเปลี่ยนได้ กระบวนการนี้จะดำเนินต่อไปจนกว่าช่องว่างทั้งหมดจะถูกเติมเต็ม
เมื่อกำหนดสถานะเริ่มต้นของทางเดิน งานของคุณคือการหา "คะแนนความงาม" สุดท้าย — ความยาวของช่วงหินอ่อนสีขาวที่ติดกันยาวที่สุด — โดยสมมติว่าสถาปนิกทั้งสองเล่นอย่างเหมาะสมที่สุดเพื่อบรรลุเป้าหมายด้านความงามของตนเอง
ข้อมูลนำเข้า
มีข้อมูลทดสอบหลายชุด บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แสดงจำนวนชุดข้อมูลทดสอบ สำหรับข้อมูลทดสอบแต่ละชุด:
บรรทัดแรกและบรรทัดเดียวประกอบด้วยสตริง $s_1 s_2 \dots s_n$ ความยาว $n$ ($1 \le n \le 10^5$) โดยที่:
0แทนช่องที่มีหินอ่อนสีขาวของ Kotori อยู่แล้ว1แทนช่องที่มีหินแกรนิตสีดำของ Umi อยู่แล้ว?แทนช่องที่ว่างอยู่ในปัจจุบัน
รับประกันว่าผลรวมของ $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