Maximum Rounding

2000ms

262144K

Description:

Given a natural number $$$x$$$. You can perform the following operation:

choose a positive integer $$$k$$$ and round $$$x$$$ to the $$$k$$$-th digit

Note that the positions are numbered from right to left, starting from zero. If the number has $$$k$$$ digits, it is considered that the digit at the $$$k$$$-th position is equal to $$$0$$$.

The rounding is done as follows:

if the digit at the $$$(k-1)$$$-th position is greater than or equal to $$$5$$$, then the digit at the $$$k$$$-th position is increased by $$$1$$$, otherwise the digit at the $$$k$$$-th position remains unchanged (mathematical rounding is used).
if before the operations the digit at the $$$k$$$-th position was $$$9$$$, and it should be increased by $$$1$$$, then we search for the least position $$$k'$$$ ($$$k'>k$$$), where the digit at the $$$k'$$$-th position is less than $$$9$$$ and add $$$1$$$ to the digit at the $$$k'$$$-th position. Then we assign $$$k=k'$$$.
after that, all digits which positions are less than $$$k$$$ are replaced with zeros.

Your task is to make $$$x$$$ as large as possible, if you can perform the operation as many times as you want.

For example, if $$$x$$$ is equal to $$$3451$$$, then if you choose consecutively:

$$$k=1$$$, then after the operation $$$x$$$ will become $$$3450$$$
$$$k=2$$$, then after the operation $$$x$$$ will become $$$3500$$$
$$$k=3$$$, then after the operation $$$x$$$ will become $$$4000$$$
$$$k=4$$$, then after the operation $$$x$$$ will become $$$0$$$

To maximize the answer, you need to choose $$$k=2$$$ first, and then $$$k=3$$$, then the number will become $$$4000$$$.

Input:

The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

Each test case consists of positive integer $$$x$$$ with a length of up to $$$2 \cdot 10^5$$$. It is guaranteed that there are no leading zeros in the integer.

It is guaranteed that the sum of the lengths of all integers $$$x$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output:

For each set of input data, output the maximum possible value of $$$x$$$ after the operations. The number should not have leading zeros in its representation.

Sample Input:

10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

Sample Output:

1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000

Note:

In the first sample, it is better not to perform any operations.

In the second sample, you can perform one operation and obtain $$$10$$$.

In the third sample, you can choose $$$k=1$$$ or $$$k=2$$$. In both cases the answer will be $$$100$$$.

Informação

Provedor Codeforces

Código CF1857B