D. Слон Филимон и цифра три
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все знают, что Индийский Слон Филимон большой фанат цифры 3.

Слон считает число красивым, если оно состоит из цифр не превосходящих 3, то есть из 0, 1, 2 и 3.

У Филимона есть натуральное число $$$n$$$. За одну операцию он может прибавить к текущему значению числа $$$n$$$ любое натуральное число, десятичная запись которого состоит исключительно из его любимой цифры 3 (например, 3, 33, 333, 3333 и так далее).

Помогите Слону Филимону определить минимальное число операций, необходимое, чтобы сделать число $$$n$$$ красивым.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t~(1 \le t \le 1000)$$$  — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка набора входных данных содержит число $$$n$$$ ($$$1 \le n \lt 10^{10^7}$$$).

Обозначим за $$$\operatorname{len}(n)$$$ количество цифр в десятичной записи числа $$$n$$$. Гарантируется, что сумма $$$\operatorname{len}(n)$$$ по всем наборам входных данных не превосходит $$$10^7$$$.

Выходные данные

Для каждого набора входных данных выведите одно число: ответ на задачу. Можно показать, что в ограничениях задачи, ответ всегда существует и не превосходит $$$2^{63}$$$.

Система оценки

Тесты к этой задаче состоят из десяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых для неё групп. Знак $$$\sum$$$ обозначает сумму по всем наборам входных данных.

ГруппаБаллыДоп. ограничения
16$$$t \le 10; n \le 3000$$$–
27$$$n \le 3 \cdot 10^5$$$1
311$$$t \le 10; nlt; 10^9$$$1
49$$$nlt; 10^9$$$2, 3
55Ответ не превосходит 2–
613$$$\sum \operatorname{len}(n) \le 60$$$1
717$$$\sum \operatorname{len}(n) \le 300$$$3, 6
812$$$\sum \operatorname{len}(n) \le 3000$$$7
911$$$\sum \operatorname{len}(n) \le 10^6$$$4, 8
109–5, 9
Пример
Входные данные
10
9
34
76
91
132
337
904
2009
64557444555
1913161522101310141615
Выходные данные
1
2
2
3
0
2
3
1
5
15
Примечание

В первом тестовом примере можно прибавить число $$$3$$$, и $$$9 + 3 = 12$$$ будет красивым числом.

Во втором примере можно добавить $$$33$$$ и $$$33$$$, получив число $$$100$$$.

В третьем примере можно добавить $$$3$$$ и $$$33$$$, получив число $$$112$$$.