给定一个自然数$$$x$$$。您可以执行以下操作:
- 选择一个正整数 $$$k$$$ 并将 $$$x$$$ 舍入到第 $$$k$$$ 位
请注意,位置从右到左编号,从零开始。如果数字有$$$k$$$位,则认为第$$$k$$$位的数字等于$$$0$$$。
舍入如下:
- 如果第 $$$(k-1)$$$ 位的数字大于或等于 $$$5$$$,则第 $$$k$$$ 位的数字增加 $$$1$$$,否则第 $$$k$$$ 位的数字保持不变(使用数学舍入)。
- 如果在操作之前第 $$$k$$$ 位的数字是 $$$9$$$,并且应该增加 $$$1$$$,那么我们搜索最小位置 $$$k'$$$ ($$$k'>k$$$),其中第 $$$k'$$$ 位的数字小于 $$$9$$$ 并将 $$$1$$$ 添加到第 $$$k'$$$ 位的数字。然后我们分配$$$k=k'$$$。
- 之后,所有位置小于 $$$k$$$ 的数字都被替换为零。
如果您可以根据需要多次执行该操作,则您的任务是使 $$$x$$$ 尽可能大。
例如,如果 $$$x$$$ 等于 $$$3451$$$,那么如果连续选择:
- $$$k=1$$$,则运算后$$$x$$$将变为$$$3450$$$
- $$$k=2$$$,则运算后$$$x$$$将变为$$$3500$$$
- $$$k=3$$$,则运算后$$$x$$$将变为$$$4000$$$
- $$$k=4$$$,则运算后$$$x$$$将变为$$$0$$$
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例由正整数 $$$x$$$ 组成,长度最大为 $$$2 \cdot 10^5$$$。确保整数中没有前导零。
保证所有测试用例中所有整数 $$$x$$$ 的长度总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每组输入数据,运算后输出$$$x$$$的最大可能值。该数字在其表示形式中不应有前导零。
示例
输入 #1
10 1 5 99 913 1980 20444 20445 60947 419860 40862016542130810467
输出 #1
1 10 100 1000 2000 20444 21000 100000 420000 41000000000000000000
注意
在第一个示例中,最好不要执行任何操作。
在第二个示例中,您可以执行一次操作并获得$$$10$$$。
在第三个示例中,您可以选择 $$$k=1$$$ 或 $$$k=2$$$。在这两种情况下,答案都是 $$$100$$$。