题目描述

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

我们称一个字符串是“美丽的”，如果无法从中选出若干个字符（可以按任意顺序排列），从而组成一个能被 $4$ 整除的数字。例如，字符串 31、222 是美丽的；而字符串 143、3123、1322 不是。特别的，空字符串也被认为是美丽的。

你的任务是计算最少需要从字符串 $s$ 中删除多少个字符，才能使其变得美丽。

输入格式

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

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

输出格式

对于每个测试用例，输出一行一个整数，表示最少需要从字符串 $s$ 中删除的字符数量，以使其变得美丽。

样例输入 1

6
4
13
21
3244123
24424224242
4132423432241231

样例输出 1

1
0
1
4
5
9

说明

样例解释

• 在第一个样例中，你必须删除整个字符串（即删除 $1$ 个字符 4）。
• 在第三个样例中，字符串 13 本身已经是美丽的，不需要删除任何字符。
• 在第四个样例中，你可以删除第 $2$、第 $3$、第 $4$ 和第 $6$ 个字符，这样你会得到美丽的字符串 313，共删除了 $4$ 个字符。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le |s| \le 3 \cdot 10^5$。
• 保证所有测试用例中 $s$ 的长度之和不超过 $3 \cdot 10^5$。