E. Сумма цифр (и опять)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для положительного (строго больше $$$0$$$) числа $$$x$$$ строка $$$S(x)$$$ формируется в результате следующего процесса:

  1. изначально эта строка пустая;
  2. затем к ней приписывается справа десятичная запись числа $$$x$$$ без ведущих нулей;
  3. после этого, если $$$x \le 9$$$, процесс заканчивается. Иначе $$$x$$$ заменяется на сумму цифр $$$x$$$, и процесс возвращается к шагу $$$2$$$;

Например:

  • $$$S(75)$$$ — это 75123;
  • $$$S(30)$$$ — это 303;
  • $$$S(9)$$$ — это 9.

Дана строка $$$s$$$, состоящая из цифр. Ваша задача — переставить символы в этой строке так, чтобы получилась строка $$$S(x)$$$ для какого-то числа $$$x$$$. Удалять символы и/или добавлять новые символы запрещено. Если заданная строка $$$s$$$ уже является строкой $$$S(x)$$$ для какого-то числа $$$x$$$, вы можете оставить ее без изменений.

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

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

Каждый набор входных данных состоит из одной строки, содержащей $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — последовательность из цифр.

Дополнительные ограничения на входные данные:

  • сумма длин $$$s$$$ по всем наборам входных данных не превосходит $$$10^5$$$;
  • можно переставить цифры в $$$s$$$ так, чтобы получить $$$S(x)$$$ для какого-то числа $$$x$$$.
Выходные данные

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

Пример
Входные данные
5
12735
1
011
99999299999999299959999999999999
4621467
Выходные данные
75123
1
101
99999999999999999999999999992529
6442167