B. 数字字符串 / Digit String

题目描述

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

如果一个字符串 不可能 选出其中若干元素（保持原顺序）组成一个能被 $4$ 整除的数，则称该字符串是 优美的。例如，字符串 31、222、213 是优美的，而 143、3123、1322 不是。空字符串被认为是优美的。

请你计算最少需要删除 $s$ 中多少个元素，才能使其成为优美的。

输入格式

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

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

额外限制：所有测试用例中 $s$ 的长度之和不超过 $3 \cdot 10^5$。

输出格式

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

样例

5
4
13
1322
222
31

1
0
2
0
0

提示

第一个例子中，需要删除整个字符串。 第二个例子中，字符串已经是优美的。 第三个例子中，删除第 $1$、$3$、$4$ 和第 $6$ 个字符，得到字符串 213。