У вас есть строка \(s\), состоящая из цифр от \(0\) до \(9\) включительно. Вы можете произвести над ней следующую операцию любое (возможно нулевое) количество раз:
Какую лексикографически минимальную строку вы можете получить после этих операций?
Строка \(a\) лексикографически меньше строки \(b\) той же длины, если и только если выполняется следующее:
В первой строке задано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Затем следуют сами наборы входных данных.
Каждый набор входных данных состоит из одной строки, содержащей строку \(s\) (\(1 \le |s| \le 2 \cdot 10^5\)) — строка из цифр. Обратите внимание, что \(s\) это просто строка, состоящая из цифр, поэтому ведущие нули разрешены.
Гарантируется, что сумма длин строки \(s\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Выведите единственную строку — лексикографически минимальную строку, которую можно получить.
В первом наборе входных данных:
Во втором и третьем наборах входных данных не нужно ничего делать.
4 04829 9 01 314752277691991
02599 9 01 111334567888999
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач