All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK113/hindi/PRFYIT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK113/mandarin/PRFYIT.pdf), [Russian](http://www.codechef.com/download/translated/COOK113/russian/PRFYIT.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK113/vietnamese/PRFYIT.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK113/bengali/PRFYIT.pdf) as well. We say that a binary string (a string containing only characters '0' and '1') is *pure* if it does not contain either of the strings "0101" or "1010" as a subsequence. Recall that string T is a subsequence of string S if we can delete some of the letters of S (possibly none) such that the resulting string will become T. You are given a binary string $S$ with length $N$. We want to make this string pure by deleting some (possibly zero) characters from it. What is the minimum number of characters we have to delete? ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains a single string $S$ with length $N$. ### Output For each test case, print a single line containing one integer — the minimum number of characters we have to delete from $S$. ### Constraints - $1 \le T \le 40$ - $1 \le N \le 1,000$ - $S$ contains only characters '0' and '1' ### Example Input ``` 4 010111101 1011100001011101 0110 111111 ``` ### Example Output ``` 2 3 0 0 ``` ### Explanation **Example case 1:** We can delete the first and third character of our string. There is no way to make the string pure by deleting only one character. **Example case 3:** The given string is already pure, so the answer is zero.
|Tags||bruteforce, cook113, dynamic-programming, easy, kmaaszraa, kmaaszraa|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.