n = int(input())
for x in range(n):
    a = input()
    s = [int(i) for i in a]
    for i in range(1, len(s)):
        j = i
        while j >= 1:
            a = s[j] - 1
            if a > s[j-1]:
                s[j] = s[j-1]
                s[j-1] = a
                j -= 1
            else:
                break     
    print(''.join([str(i) for i in s]))