Frank recibió la siguiente tarea. El tiene una cadena de texto "C" compuesta de números enteros y debe realizar la siguiente busqueda. Leer cada uno de los digitos de la cadena y encontrar el número de un solo dígito que sea mayor que el resto, esta tarea puede parecer muy simple salvo que la cadena de números puede ser demasiado grande, ayuda a Frank a hacer la siguiente operacion.

Frank debe imprimir como respuesta un número, el número de un solo dígito que haya encontrado en la cadena despues de la busqueda.

Nota: Para leer la cadena de números no use variables enteras, es recomendable leerlo como una cadena de texto.

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):

La única línea contiene la cadena de números C, cuya longitud de estará entre 1 y 10000 caracteres ambos inclusive.

Output

Imprimir un número, que será el número encontrado tras la busqueda.

Entrada de ejemplo