Problem Description

You are given an integer $n$. You need to perform $m$ operations on this number. Here, $m$ is the number of digits of the current number to be operated on (by default, the natural number $0$ is a one-digit number), and it may change as $n$ changes.

For the $i$-th operation $(1\leqslant i \leqslant m)$, you can choose one of the following three options:

1. $n\gets n+10^{i-1}$.
2. $n\gets n-10^{i-1}$.
3. $n$ remains unchanged.

You need to maximize the sum of the digits of the number after all operations.

Input Format

This problem contains multiple sets of testdata in one test file.

The first line contains a positive integer $T$, meaning there are $T$ test cases.

The next $T$ lines each contain an integer $n$.

Output Format

Output $T$ lines. Each line contains one integer, meaning the maximum possible sum of digits of $n$ after the operations for that test case.

4
33
2023
10
0

8
18
9
1

Hint

Sample Explanation.

• For $33$, choose operation 1 each time, and you get the maximum value $4+4=8$.
• For $2023$, choose operation 1 for the first, second, and fourth operations, and choose operation 2 for the third operation, getting $2+9+3+4 = 18$.
• For $10$, choose operation 2 to get $9$. At this time, $m$ becomes $1$. Since you have already performed one operation, you do not perform any more operations.
• For $0$, just choose operation 1.

Constraints.

For $30\%$ of the testdata, $1 \leqslant T \leqslant10^4$, $0 \leqslant n \leqslant 10^4$.

For $100\%$ of the testdata, $1 \leqslant T \leqslant 10^5$, $0 \leqslant n \leqslant 10^9$.

Staff.

Translated by ChatGPT 5