B. Максимальное округление
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано натуральное число $$$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$$$
Для максимизации ответа нужно сначала выбрать $$$k=2$$$, а затем $$$k=3$$$, тогда число станет равным $$$4000$$$.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

В каждом наборе входных данных дано натуральное число $$$x$$$ длиной до $$$2 \cdot 10^5$$$, гарантируется, что в записи числа нет ведущих нулей.

Гарантируется, что сумма длин чисел $$$x$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимально возможное значение $$$x$$$ после операций. В записи числа не должно быть ведущих нулей.

Пример
Входные данные
10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467
Выходные данные
1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000
Примечание

В первом примере лучше не выполнять никаких операций.

Во втором примере вы можете выполнить одну операцию и получить $$$10$$$.

В третьем примере можно выбрать $$$k=1$$$ или $$$k=2$$$. В обоих случаях ответ будет $$$100$$$.