Se da una cadena $S$ formada por letras minúsculas inglesas y una cadena $T$ inicialmente vacía.

Debes realizar operaciones sobre $S$ hasta que quede vacía. En cada paso puedes realizar una de las tres operaciones siguientes:

• Borrar el primer carácter de $S$ y añadirlo al final de $T$.
• Borrar el último carácter de $S$ y añadirlo al final de $T$.
• Elegir cadenas no vacías $A,B$ que cumplan $S=ABA^R$, establecer $S=B$ y añadir la cadena $A$ al final de $T$.

Aquí, $A^R$ representa la cadena $A$ invertida.

Halla la cadena $T$ lexicográficamente menor que se pueda obtener entre todas las secuencias de operaciones.

Entrada

Este problema contiene varios casos de prueba.

La primera línea contiene un entero positivo $t$ ($1\le t\le 10^5$), que representa el número de casos de prueba.

Para cada caso de prueba:

Una línea contiene una cadena $S$ formada por letras minúsculas ($1\le |S|\le 5\times 10^5$).

Se garantiza que la suma de $|S|$ en todos los casos de prueba no supera $5\times 10^5$.

Salida

Para cada caso de prueba, imprime en una línea una cadena que represente la respuesta.

Ejemplos

Entrada 1

6
cba
zayaz
aaaaa
xazbx
ababa
aa

Salida 1

abc
zaay
aaa
xabz
aaba
aa