题目描述

给你一个整数 $n$，你需要对这个数进行 $m$ 次操作。其中 $m$ 为当前需要操作的数的位数（默认自然数 $0$ 是一位数），且可能随着 $n$ 的改变而改变。

第 $i$ $(1\leqslant i \leqslant m)$ 次操作有以下三种选择：

1. $n\gets n+10^{i-1}$。
2. $n\gets n-10^{i-1}$。
3. $n$ 不变。

要求最大化操作后的各个数位上数字之和。

输入格式

本题一个测试点中含有多组测试数据。

第一行一个正整数 $T$，代表有 $T$ 组数据。

接下来的 $T$ 行，每行包含一个整数 $n$。

输出格式

共 $T$ 行，每行一个整数，表示每组数据的 $n$ 经操作后最大的各个数位上数字之和。

样例

4
33
2023
10
0

8
18
9
1

提示

【样例解释】

• 对于 $33$，每次操作都选择操作 $1$，得到最大值 $4+4=8$。
• 对于 $2023$，第一、二、四次操作都选择操作 $1$，第三次操作选择操作 $2$，得到 $2+9+3+4 = 18$。
• 对于 $10$，选择操作 $2$，得到 $9$，此时 $m$ 变为 $1$。因为已经操作了一次，所以不再操作。
• 对于 $0$，选择操作 $1$ 即可。

【数据范围】

对于 $100\%$ 的数据，$1 \leqslant T \leqslant 10^5$，$0 \leqslant n \leqslant 10^9$。