Додатне ціле число називається числом bobo, якщо його десятковий запис можна отримати з'єднанням двох копій одного й того самого цілого числа. Наприклад, $12341234$ і $3232$ є числами bobo, а $1234321$ і $1322$ — ні.
Додатне ціле число називається майже числом bobo, якщо після об'єднання всіх послідовних однакових цифр отримане число є числом bobo. Наприклад, $\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ після об'єднання всіх послідовних однакових цифр перетворюється на $123123$, тому є майже числом bobo.
Bobo має дуже велике число $n$ і хоче дізнатися найбільше майже число bobo, менше за $n$.
Вхідні дані
Вхідні дані містять нуль або більше тестових випадків і завершуються кінцем файлу. Для кожного тестового випадку:
Перший рядок містить ціле число $n$ без початкових нулів ($1\le n\le10^{5\,000\,000}$).
Гарантується, що сумарна довжина десяткових записів усіх $n$ у вхідних даних не перевищує $5\,000\,000$.
Вихідні дані
Для кожного тестового випадку виведіть ціле число без початкових нулів — найбільше майже число bobo, строго менше за $n$. Якщо такого цілого числа немає, натомість виведіть $-1$.
Приклади
Вхідні дані 1
12345 67890 11111 1000 26782641
Вихідні дані 1
12212 67767 11010 -1 26777267