B. Цифровая строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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$$$-й, $$$3$$$-й, $$$4$$$-й и $$$6$$$-й символы, в результате получится строка 213.