C. Пенальти
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим упрощенную фазу пенальти в конце футбольного матча.

Фаза пенальти состоит из не более чем $$$10$$$ ударов: первый удар выполняет первая команда, второй удар выполняет вторая команда, третий удар выполняет первая команда, и так далее. Команда, забившая больше голов, выигрывает; если обе команды забили одинаковое количество голов, объявляется ничья (обратите внимание, что это противоречит официальным правилам футбола). Фазу пенальти останавливают, если одна команда забила больше мячей, чем другая команда может забить с учетом всех оставшихся ударов. Например, если после $$$7$$$-го удара возникла следующая ситуация: первая команда забила $$$1$$$ мяч, а вторая команда забила $$$3$$$ мяча, то фазу пенальти останавливают: первая команда уже не сможет забить $$$3$$$ мяча за всю фазу пенальти.

Вы знаете, кто выполняет какой удар, поэтому можете спрогнозировать результаты всех $$$10$$$ ударов. Этот прогноз представлены строкой $$$s$$$, состоящей из $$$10$$$ символов. Каждый символ — 1, 0, или ?. Строка задает ваш прогноз следующим образом:

  • если $$$s_i$$$ — 1, то игрок, выполняющий $$$i$$$-й удар, обязательно забьет гол;
  • если $$$s_i$$$ — 0, то игрок, выполняющий $$$i$$$-й удар, обязательно не забьет гол;
  • если $$$s_i$$$ — ?, то результат $$$i$$$-го удара может быть любым.

Основываясь на этом прогнозе, посчитайте минимально возможное количество ударов в фазе пенальти (то есть самый ранний момент, когда фаза пенальти может быть остановлена, если рассмотреть все возможные варианты, как она может проходить). Обратите внимание, что при остановке фазы пенальти ваши прогнозы на следующие удары не учитываются.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных.

Каждый набор входных данных задается одной строкой $$$s$$$, состоящей из ровно $$$10$$$ символов. Каждый символ — 1, 0 или ?.

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

Для каждого набора входных данных выведите одно целое число — минимально возможное количество ударов в фазе пенальти.

Пример
Входные данные
4
1?0???1001
1111111111
??????????
0100000000
Выходные данные
7
10
6
9
Примечание

Рассмотрим примеры:

В первом примере, рассмотрим ситуацию, когда $$$1$$$-й, $$$5$$$-й и $$$7$$$-й забивают, а $$$2$$$, $$$3$$$, $$$4$$$ и $$$6$$$ не забивают. Тогда текущее количество голов для первой команды это $$$3$$$, а для второй команды это $$$0$$$, при этом рефери понимает, что вторая команда забьет не более $$$2$$$ голов в оставшихся ударах. Таким образом, серия пенальти закончится после $$$7$$$-го удара.

Во втором примере, серия пенальти не закончится, пока не будут совершены все $$$10$$$ ударов.

В третьем примере, если первая команда не забьет три своих первых удара, а вторая команда забьет три своих первых удара, то после $$$6$$$-го удара, первая команда забила $$$0$$$ голов и вторая команда забила $$$3$$$ гола. Рефери понимает, что первая команда может забить не более $$$2$$$ голов в оставшихся ударах. Таким образом, серия пенальти закончится после $$$6$$$-го удара.

В четвертом примере, несмотря на то, что вы можете предсказать всю серию пенальти, ее результат будет точно известен только после $$$9$$$-го удара.