给定一个整数 $$$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
注意
示例的第一个测试用例已在语句中进行了解释。
在第二个测试用例中,只有一种可能的减少:第一个和第二个数字。