建築とは往々にして、2 人の才気あふれる、しかし相反する思想を持つ人物の衝突から生まれるものです。新しい大都市の遊歩道の主任建築家であることり（Kotori）と海未（Umi）は、舗装の美学的方向性をめぐって行き詰まっています。この遊歩道は、1 列に並んだ $n$ 個のマスとしてモデル化されています。

いくつかのマスはすでに舗装されています。ことりの象徴である白い大理石が敷かれているマスもあれば、海未が好む黒い花崗岩が敷かれているマスもあります。多くのマスはまだ空のまま（「?」と表記）です。ことりと海未は、残りのマスを 1 つずつ埋めていかなければなりません。

協力における完全な公平性を保ち、どちらか一方の哲学が無競争で支配的になるのを防ぐため、2 人は正式な設計プロトコルに合意しました：

• ことりと海未は交互に、空いているマスを 1 つ選んで石を 1 つ置く。ことりが先手である。
• ことりは常に白い大理石を置く。彼女は遊歩道の美しさが白い大理石の最長の連続区間の長さによって測られると信じており、当然この長さを最大化しようとする。
• 構造的なコントラストとリズムを生み出そうとする海未は、長く途切れない白い区間は単調であると考えている。彼女は常に黒い花崗岩を置き、その同じ最大長を最小化することを目指す。

一度置かれた石は、移動したり置き換えたりすることはできません。すべての空きマスが埋まるまでこの手順が続けられます。

遊歩道の初期状態が与えられたとき、2 人の建築家がそれぞれの美学的目標を達成するために最適に行動すると仮定して、最終的な「美学的スコア」——すなわち白い大理石の最長の連続区間の長さ——を求めることがあなたの仕事です。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^4$）が与えられます。各テストケースについて：

1 行目（唯一の行）には、長さ $n$（$1 \le n \le 10^5$）の文字列 $s_1 s_2 \dots s_n$ が与えられます。ここで：

• 0 はすでにことりの白い大理石が置かれているマスを表します。
• 1 はすでに海未の黒い花崗岩が置かれているマスを表します。
• ? は現在空いているマスを表します。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されています。

出力

各テストケースについて、ゲームの最終スコアを表す整数を 1 行に出力してください。

入出力例

入力例 1

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

出力例 1

1
3
0
3
5
5