Maximum Rounding
Contest: Codeforces Round 891 (Div. 3)
Difficulty rating: 1100
Tags: greedy, implementation, math

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$$$

Input format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

Example output:
1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000

Editorial:
First, sorry for the unclear statement. We have rewritten it for several times and have chosen the best one.
Let's define $$$n$$$ as the length of the $$$x$$$.
Notice, that after applying the rounding to $$$k$$$, all the digits to the right of $$$k$$$ become $$$0$$$. If the $$$k$$$-th digit is less than $$$5$$$, after the rounding it'll only worsen the answer.
On the other side, if the $$$k$$$-th digit is not less than $$$5$$$, than rounding to the $$$k$$$-th digit always leads to better answer, because after the operation $$$x$$$ will increase.
From these observations, we can come up with the following greedy algorithm: look through all $$$k$$$ from $$$1$$$ to $$$n$$$, and if the $$$k$$$-th digit is not less than $$$5$$$, we use the rounding operation adding one to the ($$$k+1$$$)-th digit. And don't worry if that digit which must be increased by one is $$$9$$$, because in such case we always use the rounding operation on the next step.