Дана строка \(s\), состоящая из символов 0 и/или 1.
Вы должны удалить несколько (возможно, ноль) символов из начала строки и несколько (возможно, ноль) символов с конца. Получившаяся строка может оказаться пустой. Стоимость удаления — это максимум из двух величин:
Чему равна минимальная стоимость удаления, которую можно достигнуть?
В первой строке задано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из единственной строки \(s\) (\(1 \le |s| \le 2 \cdot 10^5\)), состоящей из символов 0 и/или 1.
Сумма длин \(s\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — минимальную возможную стоимость удаления.
Рассмотрим наборы входных данных из примера:
5 101110110 1001001001001 0000111111 00000 1111
1 3 0 0 0
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач