Yes, that's another problem with definition of "beautiful" numbers.

Let's call a positive integer *x* beautiful if its decimal representation without leading zeroes contains even number of digits, and there exists a permutation of this representation which is palindromic. For example, 4242 is a beautiful number, since it contains 4 digits, and there exists a palindromic permutation 2442.

Given a positive integer *s*, find the largest beautiful number which is less than *s*.
The first line contains one integer *t* (1 ≤ *t* ≤ 10<sup class="upper-index">5</sup>) — the number of testcases you have to solve.

Then *t* lines follow, each representing one testcase and containing one string which is the decimal representation of number *s*. It is guaranteed that this string has even length, contains no leading zeroes, and there exists at least one beautiful number less than *s*.

The sum of lengths of *s* over all testcases doesn't exceed 2·10<sup class="upper-index">5</sup>.
none
4
89
88
1000
28923845
88
77
99
28923839
1
100001
9999
2
1001
100001
99
9999
3
100001
100000
100002
9999
9999
100001
1
1001
99
60
799032
1880
489633
167604
641858
521214
951107
121088
952294
514428
890184
883033
317778
456130
373364
404297
757369
815335
317046
148887
834163
990592
721319
402371
458279
570263
887791
365893
433095
463049
457336
669570
803506
178817
214599
213431
895767
399711
416813
943019
190514
265042
233594
830330
529328
986218
678464
825445
854483
730167
418496
603658
981987
700630
272130
174137
220085
199466
570950
931425
799007
1818
489498
167176
641641
521152
950950
121020
952259
514415
890098
883030
317731
455994
373337
404220
757353
815185
316631
148841
833998
990550
721271
402240
457754
570075
887788
365653
433040
462642
456654
669559
803380
178781
214421
213321
895598
399663
416641
942942
190190
264642
233552
830308
529295
985985
677996
825285
854458
730073
418481
603630
981981
700575
272117
173731
220077
199441
570750
931391
11
12
3030
3112
9900
10000000000000000000000000000000000000000000
99771122997711229977112299778700000006
9999999999999999999999999999999999
1282388888999998888888888988
10101010999999999999999999
28383928391839821938
938883833333333333
11
3003
3030
9898
999999999999999999999999999999999999999999
99771122997711229977112299778699999986
9999999999999999999999999999999988
1282388888999998888888888931
10101010999999999999999988
28383928391839821928
938883833333333292
1
1010
1001
4
12
1000
1001
1002
11
99
99
1001
1
7976
7887
6
12
10000000000000000000000000000000000000000000
3030
3112
99771122997711229977112299778700000006
99771122997711229977112299778699999996
11
999999999999999999999999999999999999999999
3003
3030
99771122997711229977112299778699999986
99771122997711229977112299778699999986
1
10000001
999999
from sys import stdin, stdout

def solve(X):
    # se convierte el numero a su representación decimal
    X_s = str(X)
    # prefijo construido del numero hermos que es respuesta
    p = ""

    # contar la cantidad de cifras distintas de 0 desde el 
    # inicio hasta el final.
    count_dif_zero = [0]
    for i in range(len(X_s)):
        count_dif_zero.append(count_dif_zero[-1] + (int(X_s[i]) > 0))
    
    # si el número s es de tipo 100...00 entonces el numero 
    # hermoso mayor que es menor que él es 99...99 con tamaño
    # n - 2, donde n es el tamaño del número original
    if X_s[0] == '1' and count_dif_zero[len(X_s)] == 1:
        return "9" * (len(X_s) -2)

    # si el número es de la forma 100...01 entonces el número
    # hermoso mayor que es menor que él es 99...99 con tamaño 
    # n - 2 donde n es el tamaño del número original.
    if X_s[0] == '1' and X_s[len(X_s) -1] == '1' and count_dif_zero[len(X_s)] == 2:
        return "9" * (len(X_s) -2)
    
    rho = [0] * 10
    for i in range(len(X_s)):
        # mientras no se ha llegado a la última posicion de s
        # entonces vamos contar el digito, vamos a verificar 
        # si se puede utilizar, de poderse entonces se utiliza, 
        # si no se resta su uso.
        if i < len(X_s) -1:
            # se cuenta
            rho[int(X_s[i])] ^= 1
            # se verifica que se puede añadir
            if check(i + 1, X_s, rho, count_dif_zero):
                
                # se añade y se pasa a la proxima iteracion
                p += X_s[i]
                continue
            # se elimina su uso
            rho[int(X_s[i])] ^= 1
        
        # como no se pudo utilizar en el sufijo entonces se 
        # se añade el menor numero al prefijo con el que se
        # consiga un sufijo que haga ps hermoso
        for di in range(int(X_s[i])-1, -1, -1):
            
            # se cuenta su uso
            rho[di] ^= 1
            
            
            # si se puede encontrar el sufijo, entonces se
            # se añade dicho digito al prefijo
            if can(i + 1, rho, len(X_s)):
                # se añade
                p += str(di)
                # se añade el sufijo encontrado
                p = fix(i + 1, p, rho, len(X_s))
                break
            # se elimina su uso
            rho[di] ^= 1
        break
    
    return p

def check(pos, s, rho, count_0):
    # este metodo devuelve si es posible utilizar s[pos] 
    # en el prefijo que se ha construido.

    # suma la cantidad de digitos con cantidad de
    # repeticiones impar
    c = sum(rho)

    # si restan c digitos por poner para que estos 
    # tengan rho par, y quedan menos posiciones entonces
    # no es posible.
    if c > len(s) - pos:
        return False
    
    # si hasta pos se tienen menos posiciones diferente
    # de cero que hasta n - c entonces se puede utilizar
    # la posicion pos del numero original, pues si son 
    # iguales esto es que en el numero original entonces 
    # desde pos hasta n - c todo es 0 y es necesario hacer
    # otras verificaciones, y no puede ser mayor porque
    # count_0 es un array no decreciente.
    if count_0[len(s) - c] - count_0[pos] > 0:
        return True
    
    # aqui se almacena el proximo dígito con rho impar
    # a analizar, esto es que que si en la posicion i 
    # el primer digito con rho impar es menor que el 
    # valor en la posicion original entonces se puede
    # poner el valor s[pos] y luego utilizar next en 
    # dicha posicion para obtener un numero hermoso 
    # menor. Pero si el primer digito tiene mayor valor
    # entonces como sea que se rellene siempre se llega
    # a un numero hermoso mayor. Por tanto, no se puede
    # utilizar s[pos]. Si el digito y s[pos] tienen igual
    # valor no se sabe si se puede construir, se tiene que
    # que analizar la siguiente posicion.
    next = 0
    for i in range(len(s)-c, len(s)):
        # buscar el primer digito con rho impar
        while rho[next] == 0:
            next += 1
        # si s[i] > que el digito se puede
        if int(s[i]) > next:
            return True
        # si s[i] < que el digito no se puede
        if int(s[i]) < next:
            return False
        # se pasa a analizar el siguiente digito
        next += 1
    # si se analiza todo hasta esta posicion y no se ha cumplido
    # ninguna de las condiciones entonces no se puede utilizar 
    # s[pos], pues no existe ninguna garantia de encontrar el numero
    # hermoso menor que tenga en pos a s[pos]
    return False

def can(pos, rho, n):
    # si puedo poner todos los digitos  con rho impar
    # en las posiciones sobrantes entonces es posible 
    # utilizar el digito que se quiere utilizar
    return sum(rho) <= n - pos

def fix(pos, p, rho, n):
    # encuentra el sufijo s que hace a ps el mayor numero
    # hermoso que responde a la consulta.

    c = sum(rho)

    # entonces el mayor numero hermoso es de la forma
    # p + '9...9' + todos los digitos con rho impar 
    # en orden decreciente
    p += '9' * (n - pos - c)

    # proximo digito candidato a poner en el prefijo
    next = 9
    while next >= 0:
        # si el digito tiene rho par no se puede utilizar
        # pues cambiaria su rho a impar y dejaria de se
        # hermoso el resultado
        while next >= 0 and rho[next] == 0:
            next -= 1
        if next >= 0:
            # se utiliza el digito
            p += str(next)
            # este no puede volver a usarse pues afectaria
            # su rho, si no que debe usarse un digito inferior
            next -= 1
    return p


if __name__ == "__main__":
    n = int(stdin.readline().split()[0])
    A = [int(stdin.readline().split()[0]) for n in range(n)]
    for a in A:
        stdout.write(solve(a) + "\n")