← 返回题目列表

Codeforces · 2230/B

B. 数字字符串

中文机器翻译题面 查看原题

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

假设该字符串是 美丽 如果是 不可能 选择其中的一些元素并将它们写出(按照它们在字符串中出现的顺序)以形成 $$$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
3244123
24424224242
4132423432241231

输出
复制

1
0
4
5
9

注意

在第一个示例中,您必须删除整个字符串。

在第二个示例中,字符串已经很漂亮了。

在第三个示例中,您可以删除 $$$1$$$-st、$$$3$$$-rd、$$$4$$$-th 和 $$$6$$$-th 字符,您将得到字符串 213.