Palíndromo más pequeño P21831

Implementar un programa que, para cada palabra dada, escriba el palíndromo más pequeño (en orden lexicográfico) que se puede formar usando exactamente una vez todas sus letras. Tanto las palabras dadas como los palíndromos formados no tienen porqué tener ningún sentido. Si, para alguna palabra, no es posible formar ningún palíndromo, hay que indicarlo.

Entrada

La entrada consiste en el número $k\le 1000$ de palabras en una línea, seguido de $k$ líneas, cada una con una palabra no vacía. Las palabras están formadas exclusivamente por como mucho 500 letras minúsculas.

Tu programa deberá resolver una entrada como la descrita en menos de 1 segundo.

Salida

Para cada palabra, escribir una línea con el palíndromo más pequeño que se puede formar usando exactamente una vez todas las letras de la palabra. Si no es posible formar ninguno, escribir "NINGUN PALINDROMO".