如果一個正整數嘅十進制表示，可以由同一個整數嘅兩份副本串接而成，佢就叫做 Bobo 數。例如，$12341234$ 同 $3232$ 都係 Bobo 數，但 $1234321$ 同 $1322$ 就唔係。

如果一個正整數喺將所有連續相同嘅數字合併之後，所得嘅數係 Bobo 數，佢就叫做近似 Bobo 數。例如，$\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ 喺將所有連續相同嘅數字合併之後會變成 $123123$，所以佢係一個近似 Bobo 數。

Bobo 有一個非常大嘅數 $n$，佢想知道細過 $n$ 嘅最大近似 Bobo 數。

輸入格式

輸入包含零組或多組測試資料，以檔案結尾結束。對每組測試資料：

第一行包含一個冇前導零嘅整數 $n$（$1 \le n \le 10^{5\,000\,000}$）。

保證輸入入面所有 $n$ 嘅十進制表示嘅總長度唔超過 $5\,000\,000$。

輸出格式

對每組測試資料，輸出一個冇前導零嘅整數，表示嚴格細過 $n$ 嘅最大近似 Bobo 數。如果冇咁樣嘅整數，就輸出 $-1$。

樣例

輸入格式 1

12345
67890
11111
1000
26782641

輸出格式 1

12212
67767
11010
-1
26777267