Все знают, что Индийский Слон Филимон большой фанат цифры 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$$$ обозначает сумму по всем наборам входных данных.
| Группа | Баллы | Доп. ограничения | ||
| 1 | 6 | $$$t \le 10; n \le 3000$$$ | – | |
| 2 | 7 | $$$n \le 3 \cdot 10^5$$$ | 1 | |
| 3 | 11 | $$$t \le 10; n | lt; 10^9$$$ | 1 |
| 4 | 9 | $$$n | lt; 10^9$$$ | 2, 3 |
| 5 | 5 | Ответ не превосходит 2 | – | |
| 6 | 13 | $$$\sum \operatorname{len}(n) \le 60$$$ | 1 | |
| 7 | 17 | $$$\sum \operatorname{len}(n) \le 300$$$ | 3, 6 | |
| 8 | 12 | $$$\sum \operatorname{len}(n) \le 3000$$$ | 7 | |
| 9 | 11 | $$$\sum \operatorname{len}(n) \le 10^6$$$ | 4, 8 | |
| 10 | 9 | – | 5, 9 |
1093476911323379042009645574445551913161522101310141615
12230231515
В первом тестовом примере можно прибавить число $$$3$$$, и $$$9 + 3 = 12$$$ будет красивым числом.
Во втором примере можно добавить $$$33$$$ и $$$33$$$, получив число $$$100$$$.
В третьем примере можно добавить $$$3$$$ и $$$33$$$, получив число $$$112$$$.
| Название |
|---|


