Un entero positivo se llama número bobo si su representación decimal puede obtenerse concatenando dos copias del mismo entero. Por ejemplo, $12341234$ y $3232$ son números bobo, mientras que $1234321$ y $1322$ no lo son.
Un entero positivo se llama número casi bobo si, tras fusionar todos los dígitos iguales consecutivos, el número resultante es un número bobo. Por ejemplo, $\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ se convierte en $123123$ al fusionar todos los dígitos iguales consecutivos, por lo que es un número casi bobo.
Bobo tiene un número $n$ muy grande y quiere saber cuál es el mayor número casi bobo menor que $n$.
Entrada
La entrada contiene cero o más casos de prueba y termina al llegar al final del archivo. Para cada caso de prueba:
La primera línea contiene un entero $n$ sin ceros iniciales ($1 \le n \le 10^{5\,000\,000}$).
Se garantiza que la longitud total de las representaciones decimales de todos los $n$ de la entrada no supera $5\,000\,000$.
Salida
Para cada caso de prueba, imprime un entero sin ceros iniciales que indique el mayor número casi bobo estrictamente menor que $n$. Si no existe tal entero, imprime $-1$ en su lugar.
Ejemplos
Entrada 1
12345 67890 11111 1000 26782641
Salida 1
12212 67767 11010 -1 26777267