Eine positive ganze Zahl heißt Bobo-Zahl, wenn ihre Dezimaldarstellung durch das Aneinanderhängen zweier Kopien derselben ganzen Zahl entsteht. Zum Beispiel sind $12341234$ und $3232$ Bobo-Zahlen, während $1234321$ und $1322$ keine sind.

Eine positive ganze Zahl heißt Fast-Bobo-Zahl, wenn nach dem Zusammenfassen aller aufeinanderfolgenden gleichen Ziffern die entstehende Zahl eine Bobo-Zahl ist. Zum Beispiel wird $1112223112233$ durch das Zusammenfassen aller aufeinanderfolgenden gleichen Ziffern zu $123123$ und ist daher eine Fast-Bobo-Zahl.

Bobo hat eine sehr große Zahl $n$ und möchte die größte Fast-Bobo-Zahl kennen, die kleiner als $n$ ist.

Eingabe

Die Eingabe enthält null oder mehr Testfälle und endet mit dem Dateiende. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ohne führende Nullen ($1 \le n \le 10^{5\,000\,000}$).

Es ist garantiert, dass die Gesamtlänge der Dezimaldarstellungen aller Zahlen $n$ in der Eingabe $5\,000\,000$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl ohne führende Nullen aus, welche die größte Fast-Bobo-Zahl bezeichnet, die strikt kleiner als $n$ ist. Falls es keine solche ganze Zahl gibt, gib stattdessen $-1$ aus.

Beispiele

Eingabe 1

12345
67890
11111
1000
26782641

Ausgabe 1

12212
67767
11010
-1
26777267