建筑设计往往是两位才华横溢但理念相反的设计师之间碰撞的产物。作为一条新都市漫步道的首席建筑师，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