CF2230B.Digit String

You are given a string $s$ consisting of digits from $1$ to $4$.

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.

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.

给你一个由数字 $1$ 到 $4$ 组成的字符串 $s$。

我们称该字符串是优美的，当且仅当无法从中选出若干字符（保持它们在原字符串中的相对顺序），拼接成一个能被 $4$ 整除的数。例如，字符串 31、222、213 是优美的，而字符串 143、3123、1322 不是优美的。空字符串被视为优美的。

你的任务是计算：为使字符串 $s$ 变为优美字符串，最少需要删除多少个字符。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

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$.

Additional constraint on the input: the sum of the lengths of $s$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含一个字符串 $s$（$1 \le |s| \le 3 \cdot 10^5$），由数字 $1$ 到 $4$ 组成。

输入的额外约束：所有测试用例中字符串 $s$ 的长度总和不超过 $3 \cdot 10^5$。

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.

对于每个测试用例，输出一个整数——为使字符串 $s$ 变得优美，需要删除的最少元素个数。

In the first example, you have to delete the whole string.

In the second example, the string is already beautiful.

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.

在第一个例子中，你需要删除整个字符串。

在第二个例子中，该字符串本身已经是优美的。

在第三个例子中，你可以删除第 $1$、第 $3$、第 $4$ 和第 $6$ 个字符，从而得到字符串 213。