4601: Bigger number

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 xwill become 4000
• k=4, then after the operation x will become 0

The first line contains a single integer t (1≤t≤10⁴) — the number of test cases.

Each test case consists of positive integer x with a length of up to 2⋅10⁵. 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⋅10⁵.

10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000