Архитектура часто становится результатом столкновения двух блестящих, но противоположных умов. Котори и Уми, главные архитекторы нового городского променада, зашли в тупик в вопросе эстетического направления мощения. Променад моделируется как последовательность из $n$ клеток в один ряд.

Некоторые клетки уже вымощены: в одних лежит фирменный белый мрамор Котори, а в других — предпочитаемый Уми чёрный гранит. Многие клетки остаются пустыми (отмечены символом «?»). Теперь Котори и Уми должны заполнить оставшиеся клетки одну за другой.

Чтобы обеспечить полную справедливость в совместной работе и не позволить ни одной философии доминировать без борьбы, они договорились о формальном протоколе проектирования:

• Котори и Уми по очереди кладут по одному камню в пустую клетку, причём Котори ходит первой.
• Котори всегда кладёт белый мрамор, так как считает, что красота променада измеряется его самым длинным непрерывным отрезком из белого мрамора. Естественно, она стремится максимизировать эту длину.
• Уми, стремясь обеспечить структурный контраст и ритм, считает, что длинные непрерывные белые участки монотонны. Она всегда кладёт чёрный гранит, стремясь минимизировать эту же максимальную длину.

Как только камень уложен, его нельзя передвинуть или заменить. Процесс продолжается до тех пор, пока все пустые клетки не будут заполнены.

По заданному начальному состоянию променада ваша задача — определить итоговую «Эстетическую оценку» — длину самого длинного непрерывного отрезка из белого мрамора — при условии, что оба архитектора играют оптимально для достижения своих эстетических целей.

Входные данные

Входные данные состоят из нескольких наборов. Первая строка содержит целое число $T$ ($1 \le T \le 10^4$), обозначающее количество наборов входных данных. Для каждого набора:

Первая и единственная строка содержит одну строку $s_1 s_2 \dots s_n$ длины $n$ ($1 \le n \le 10^5$), где:

• 0 обозначает клетку, в которой уже лежит белый мрамор Котори;
• 1 обозначает клетку, в которой уже лежит чёрный гранит Уми;
• ? обозначает пустую в данный момент клетку.

Гарантируется, что сумма $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