给您一个字符串 $$$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$$$ 中需要删除以使其美观的最小可能元素数。
示例
输入复制
54133244123244242242424132423432241231
输出复制
10459
注意
在第一个示例中,您必须删除整个字符串。
在第二个示例中,字符串已经很漂亮了。
在第三个示例中,您可以删除 $$$1$$$-st、$$$3$$$-rd、$$$4$$$-th 和 $$$6$$$-th 字符,您将得到字符串 213.