Um inteiro positivo é chamado de número bobo se a sua representação decimal puder ser obtida concatenando duas cópias do mesmo inteiro. Por exemplo, $12341234$ e $3232$ são números bobo, enquanto $1234321$ e $1322$ não são.
Um inteiro positivo é chamado de número quase bobo se, depois de fundir todos os algarismos iguais consecutivos, o número resultante for um número bobo. Por exemplo, $\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ transforma-se em $123123$ depois de fundir todos os algarismos iguais consecutivos e, portanto, é um número quase bobo.
Bobo tem um número muito grande $n$ e gostaria de saber qual é o maior número quase bobo menor do que $n$.
Entrada
A entrada contém zero ou mais casos de teste e termina no fim do ficheiro. Para cada caso de teste:
A primeira linha contém um inteiro $n$ sem zeros à esquerda ($1\le n\le10^{5\,000\,000}$).
É garantido que o comprimento total das representações decimais de todos os $n$ da entrada não excede $5\,000\,000$.
Saída
Para cada caso de teste, imprima um inteiro sem zeros à esquerda que represente o maior número quase bobo estritamente menor do que $n$. Se não existir tal inteiro, imprima $-1$.
Exemplos
Entrada 1
12345 67890 11111 1000 26782641
Saída 1
12212 67767 11010 -1 26777267