2230B.md (1607B)
1 Source: https://codeforces.com/problemset/problem/2230/B 2 3 B. Digit String 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a string $s$ consisting of digits from $1$ to $4$. 22 23 Let's say that the string is beautiful if it is impossible to select some of its elements and write them out (in the same order as they appear in the string) to form a number that is a multiple of $4$. For example, the strings 31, 222, 213 are beautiful, while the strings 143, 3123, 1322 are not. The empty string is considered beautiful. 24 25 Your task is to calculate the minimum possible number of elements in the string $s$ that need to be removed in order to make it beautiful. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The only line of each test case contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting of digits from $1$ to $4$. 32 33 Additional constraint on the input: the sum of the lengths of $s$ over all test cases doesn't exceed $3 \cdot 10^5$. 34 35 Output 36 37 For each test case, print a single integer — the minimum possible number of elements in the string $s$ that need to be removed in order to make it beautiful. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 4 47 48 13 49 50 3244123 51 52 24424224242 53 54 4132423432241231 55 ``` 56 57 Output 58 59 ``` 60 1 61 62 0 63 64 4 65 66 5 67 68 9 69 ``` 70 71 Note 72 73 In the first example, you have to delete the whole string. 74 75 In the second example, the string is already beautiful. 76 77 In the third example, you can delete the $1$-st, $3$-rd, $4$-th, and $6$-th characters, and you will get the string 213.