You are given a string $$$s$$$ consisting of characters 0 and/or 1.
You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values:
What is the minimum cost of removal you can achieve?
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of characters 0 and/or 1.
The total length of strings $$$s$$$ in all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print one integer — the minimum cost of removal you can achieve.
510111011010010010010010000111111000001111
1 3 0 0 0
Consider the test cases of the example:
Name |
---|