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

Дана десятичная запись целого числа $$$x$$$ без лидирующих нулей.

Требуется проделать над ним следующую операцию, называемую сжатием, ровно один раз: взять две соседние цифры в $$$x$$$ и заменить на их сумму без лидирующих нулей (если сумма равна $$$0$$$, то она представляется как один $$$0$$$).

Например, если $$$x = 10057$$$, то возможные сжатия следующие:

  • выбрать первую и вторую цифры $$$1$$$ и $$$0$$$, заменить на $$$1+0=1$$$; результат $$$1057$$$;
  • выбрать вторую и третью цифры $$$0$$$ и $$$0$$$, заменить на $$$0+0=0$$$; результат тоже $$$1057$$$;
  • выбрать третью и четвертую цифры $$$0$$$ и $$$5$$$, заменить на with $$$0+5=5$$$; результат все еще $$$1057$$$;
  • выбрать четвертую и пятую цифры $$$5$$$ и $$$7$$$, заменить на $$$5+7=12$$$; результат $$$10012$$$.

Какое наибольшее число можно получить?

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

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

Каждый набор входных данных состоит из одного целого числа $$$x$$$ ($$$10 \le x < 10^{200000}$$$). $$$x$$$ не содержит лидирующих нулей.

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

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

На каждый набор входных данных выведите одно целое число — наибольшее число, которое можно получить после применения сжатия ровно один раз. Число не должно содержать лидирующих нулей.

Пример
Входные данные
2
10057
90
Выходные данные
10012
9
Примечание

Первый набор входных данных уже объяснен в условии.

Во втором наборе входных данных есть только одно возможное сжатие: первая и вторая цифры.