Un entier strictement positif est appelé un nombre bobo si sa représentation décimale peut être obtenue en concaténant deux copies du même entier. Par exemple, $12341234$ et $3232$ sont des nombres bobo, tandis que $1234321$ et $1322$ n'en sont pas.
Un entier strictement positif est appelé un nombre presque bobo si, après fusion de tous les chiffres consécutifs identiques, le nombre obtenu est un nombre bobo. Par exemple, $\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ devient $123123$ après fusion de tous les chiffres consécutifs identiques ; il s'agit donc d'un nombre presque bobo.
Bobo possède un très grand nombre $n$ et souhaite connaître le plus grand nombre presque bobo inférieur à $n$.
Entrée
L'entrée contient zéro ou plusieurs cas de test et se termine à la fin du fichier. Pour chaque cas de test :
La première ligne contient un entier $n$ sans zéros initiaux ($1\le n\le10^{5\,000\,000}$).
Il est garanti que la longueur totale des représentations décimales de tous les $n$ de l'entrée ne dépasse pas $5\,000\,000$.
Sortie
Pour chaque cas de test, affichez un entier sans zéros initiaux représentant le plus grand nombre presque bobo strictement inférieur à $n$. S'il n'existe aucun entier de ce type, affichez $-1$ à la place.
Exemples
Entrée 1
12345 67890 11111 1000 26782641
Sortie 1
12212 67767 11010 -1 26777267