Архітектура часто стає результатом зіткнення двох блискучих, але протилежних умів. Которі та Умі, головні архітекторки нового міського променаду, зайшли в глухий кут щодо естетичного напрямку брукування. Променад моделюється як послідовність із $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