若一個正整數的十進位表示可以由同一個整數的兩份副本串接而成，就稱它為 Bobo 數。例如，$12341234$ 和 $3232$ 是 Bobo 數，而 $1234321$ 和 $1322$ 不是。

若將一個正整數中所有連續相同的數字合併後，得到的數是 Bobo 數，就稱它為近似 Bobo 數。例如，$1112223112233$ 在合併所有連續相同的數字後會變成 $123123$，因此它是近似 Bobo 數。

Bobo 有一個非常大的數 $n$，他想知道小於 $n$ 的最大近似 Bobo 數。

輸入格式

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

第一行包含一個沒有前導零的整數 $n$（$1\le n\le10^{5\,000\,000}$）。

保證輸入中所有 $n$ 的十進位表示的總長度不超過 $5\,000\,000$。

輸出格式

對每筆測試資料，輸出一個沒有前導零的整數，表示嚴格小於 $n$ 的最大近似 Bobo 數。若不存在這樣的整數，則輸出 $-1$。

範例

輸入格式 1

12345
67890
11111
1000
26782641

輸出格式 1

12212
67767
11010
-1
26777267