Parece que el año 2013 hubiera llegado ayer. Pero ¿Te has dado cuenta de un dato curioso?. El año de 2013 es el primer año después 1987 con la particularidad de que todos los dígitos que lo componen, son distintos.

Este año 2013 es un año muy especial, no solo porque ya existe Coderperu, sino por que el dato curioso de este año tambien esta en otros años a partir de este, entonces he aqui el problema: dado un número de un año, debes encontrar el número mínimo del año, que sea estrictamente mayor al que te hemos dado y que cumpla la condición de que todos sus dígitos sean distintos.

Recibirás un entero Y que será el año desde donde comenzaras tu busqueda. Ver los casos de ejemplo.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 <= M <= 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

Y : Un entero positivo que representa el número del año. (1000 ≤ Y ≤ 9000)

Output

Imprimir un único entero: el número mínimo del año que sea estrictamente mayor que Y, y que todas sus cifras sean distintas. Se garantiza que existe la respuesta.

Casos de ejemplo