Background

However, how can one slack off elegantly?

Problem Description

Kitty has several popsicle sticks arranged in a row. Each stick has a digit from $0 \sim 9$, and it is guaranteed that the digit on the leftmost stick is not $0$. Kitty thinks that these sticks, from left to right, form a decimal positive integer $n$.

Kitty thinks $0$ is wonderful, so she will try her best to turn $n$ into $0$, that is, remove all popsicle sticks.

Each time, Kitty performs one operation. In each operation, she chooses a popsicle stick whose digit is not $0$, and decreases it by $1$. After that, if there are some consecutive popsicle sticks on the far left whose digits are $0$ (that is, $n$ has leading zeros), Kitty will remove those sticks.

A little mouse will come and cause trouble. At some moment (possibly before all operations start, or possibly after any one of Kitty's operations), it will change one digit on one popsicle stick. The little mouse can change only one digit in total.

The mouse wants the number of operations to be as large as possible, while Kitty wants it to be as small as possible. Therefore, Kitty wants to know the number of operations when both of them use optimal strategies.

Input Format

This problem contains multiple test cases in a single test file.

The first line contains a positive integer $T$, the number of test cases. For each test case:

• One line containing a positive integer $n$.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

2
1100
11332132121

11
28

Hint

Sample Explanation 1

For the first test case, the mouse can change $1100$ into $1109$ at the very beginning. Then Kitty needs a total of $1 + 1 + 9$ operations to turn $n$ into $0$.

Constraints

This problem uses bundled testdata.

• Subtask 0 (13 pts): $n \leq 99$.
• Subtask 1 (13 pts): $n = 10^k$, where $k$ is a natural number.
• Subtask 2 (13 pts): $n = 10^k - 1$, where $k$ is a positive integer.
• Subtask 3 (13 pts): $n \leq 999\ 999$.
• Subtask 4 (48 pts): No special restrictions.

For all testdata, $1 \leq T \leq 3333$, $1 \leq n \leq 9\ 999\ 999\ 999\ 999(=10^{13} - 1)$. After all, Kitty can have at most $13$ popsicle sticks in one bundle.

Translated by ChatGPT 5