Everyone knows that the Indian Elephant Filimon is a big fan of the digit 3.
The elephant considers a number to be beautiful if it consists only of digits not exceeding 3, that is, digits 0, 1, 2, and 3.
Filimon has a positive integer $$$n$$$. In one operation, he can add to the current value of the number $$$n$$$ any positive integer whose decimal representation consists exclusively of his favorite digit 3 (for example, 3, 33, 333, 3333, and so on).
Help Elephant Filimon determine the minimum number of operations needed to make $$$n$$$ beautiful.
Each test consists of several test cases. The first line contains one integer $$$t~(1 \le t \le 1000)$$$ — the number of sets of input data. The description of the sets of input data follows.
The only line of the test case contains the number $$$n$$$ ($$$1 \le n \lt 10^{10^7}$$$).
Let $$$\operatorname{len}(n)$$$ denote the number of digits in the decimal representation of the number $$$n$$$. It is guaranteed that the sum of $$$\operatorname{len}(n)$$$ across all test cases does not exceed $$$10^7$$$.
For each test case, output one number: the answer to the problem. It can be shown that under the problem constraints, the answer always exists and does not exceed $$$2^{63}$$$.
The tests for this problem consist of ten groups. Points for each group are awarded only if all tests in the group and all tests necessary for it are passed. The symbol $$$\sum$$$ denotes the sum over all test cases.
| Group | Points | Additional Constraints | ||
| 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 | The answer does not exceed 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
In the first test example, you can add the number $$$3$$$, and $$$9 + 3 = 12$$$ will be a beautiful number.
In the second example, you can add $$$33$$$ and $$$33$$$, resulting in the number $$$100$$$.
In the third example, you can add $$$3$$$ and $$$33$$$, resulting in the number $$$112$$$.