建築設計往往是兩位才華橫溢但理念相反的設計師之間碰撞的產物。作為一條新都市漫步道的首席建築師，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