← 返回题目列表

Codeforces · 1626/B

B. 小幅减少

中文机器翻译题面 查看原题

给定一个整数 $$$x$$$ 的十进制表示形式,不带前导零。

您必须对其执行以下缩减操作一次:取 $$$x$$$ 中的两个相邻数字,并将它们替换为不带前导零的总和(如果总和为 $$$0$$$,则表示为单个 $$$0$$$)。

例如,如果 $$$x = 10057$$$,则可能的减少量为:

- 选择第一个和第二个数字 $$$1$$$ 和 $$$0$$$,将其替换为 $$$1+0=1$$$;结果是$$$1057$$$;
- 选择第二个和第三个数字$$$0$$$和$$$0$$$,将其替换为$$$0+0=0$$$;结果也是$$$1057$$$;
- 选择第三个和第四个数字$$$0$$$和$$$5$$$,将其替换为$$$0+5=5$$$;结果仍然是$$$1057$$$;
- 选择第四和第五位$$$5$$$和$$$7$$$,将其替换为$$$5+7=12$$$;结果是$$$10012$$$。

能得到的最大数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一个整数 $$$x$$$ ($$$10 \le x < 10^{200000}$$$) 组成。 $$$x$$$ 不包含前导零。

所有测试用例中 $$$x$$$ 的十进制表示的总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数——仅应用一次归约后可以获得的最大数字。该数字不应包含前导零。

示例

输入 #1

2
10057
90

输出 #1

10012
9

注意

示例的第一个测试用例已在语句中进行了解释。

在第二个测试用例中,只有一种可能的减少:第一个和第二个数字。