建築設計往往係兩位才華橫溢但理念相反嘅設計師之間碰撞嘅產物。作為一條新都市漫步道嘅首席建築師，Kotori 同 Umi 喺鋪磚嘅美學方向上陷入咗僵局。呢條漫步道被建模為單行排列嘅 $n$ 個格仔。

部分格仔已經鋪好咗磚：一啲格仔包含 Kotori 標誌性嘅白色大理石，而另一啲就包含 Umi 偏愛嘅黑色花崗岩。好多格仔仍然空住（標記為「?」）。Kotori 同 Umi 而家必須逐個填滿剩低嘅格仔。

為咗確保合作嘅絕對公平，並防止任何單一嘅設計理念喺冇競爭嘅情況下佔據主導地位，佢哋同意遵守一套正式嘅設計協議：

• Kotori 同 Umi 輪流將單塊石頭放入一個空格仔入面，由 Kotori 先手。
• Kotori 總係擺放白色大理石，因為佢認為漫步道嘅美感取決於其最長連續白色大理石段嘅長度。佢自然會力圖最大化呢個長度。
• Umi 旨在提供結構上嘅對比同節奏感，佢認為漫長而且唔間斷嘅白色區域係單調嘅。佢總係擺放黑色花崗岩，旨在最小化呢同一個最大長度。

石頭一旦擺放，就唔可以移動或者更換。呢個過程持續進行，直到所有空格仔都被填滿。

給定漫步道嘅初始狀態，你嘅任務係確定喺兩位建築師都為咗實現各自嘅美學目標而採取最優策略嘅情況下，最終嘅「美學評分」——即係最長連續白色大理石段嘅長度。

輸入格式

輸入包含多組測試數據。第一行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試數據嘅組數。對於每組測試數據：

第一行亦係唯一嘅一行包含一個長度為 $n$（$1 \le n \le 10^5$）嘅字串 $s_1 s_2 \dots s_n$，其中：

• 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