310595: CF1857B. Maximum Rounding

B. Maximum Roundingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExampleInput

10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

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

题目大意：
给定一个自然数x。你可以执行以下操作：
选择一个正整数k并将x四舍五入到第k位
注意，位置是从右到左编号的，从零开始。如果数字有k位，则认为第k位的数字等于0。
四舍五入操作如下：
如果第(k-1)位的数字大于或等于5，则第k位的数字加1，否则第k位的数字保持不变（使用数学四舍五入）。
如果在操作前第k位的数字是9，并且应该加1，则找到最小的位置k'（k'>k），其中第k'位的数字小于9，并将第k'位的数字加1。然后将k赋值为k'。
在此之后，所有位置小于k的数字都被替换为0。
你的任务是尽可能使x最大，如果你可以执行任意次操作。
输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例由一个长度不超过2×10^5的正整数x组成。保证整数中没有前导零。
保证所有测试用例的整数x的长度之和不超过2×10^5。
输出格式：
对于每组输入数据，输出操作后x的最大可能值。数字的表示不应包含前导零。题目大意： 给定一个自然数x。你可以执行以下操作： 选择一个正整数k并将x四舍五入到第k位 注意，位置是从右到左编号的，从零开始。如果数字有k位，则认为第k位的数字等于0。 四舍五入操作如下： 如果第(k-1)位的数字大于或等于5，则第k位的数字加1，否则第k位的数字保持不变（使用数学四舍五入）。 如果在操作前第k位的数字是9，并且应该加1，则找到最小的位置k'（k'>k），其中第k'位的数字小于9，并将第k'位的数字加1。然后将k赋值为k'。 在此之后，所有位置小于k的数字都被替换为0。 你的任务是尽可能使x最大，如果你可以执行任意次操作。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例由一个长度不超过2×10^5的正整数x组成。保证整数中没有前导零。 保证所有测试用例的整数x的长度之和不超过2×10^5。 输出格式： 对于每组输入数据，输出操作后x的最大可能值。数字的表示不应包含前导零。