Положительное целое число называется числом Bobo, если его десятичную запись можно получить, приписав друг к другу две копии одного и того же целого числа. Например, $12341234$ и $3232$ являются числами Bobo, а $1234321$ и $1322$ — нет.

Положительное целое число называется почти числом Bobo, если после объединения всех подряд идущих одинаковых цифр полученное число является числом Bobo. Например, $1112223112233$ превращается в $123123$ после объединения всех подряд идущих одинаковых цифр и поэтому является почти числом Bobo.

У Bobo есть очень большое число $n$, и он хочет узнать наибольшее почти число Bobo, меньшее $n$.

Входные данные

Входные данные содержат ноль или более тестовых случаев и завершаются концом файла. Для каждого тестового случая:

Первая строка содержит целое число $n$ без ведущих нулей ($1 \le n \le 10^{5\,000\,000}$).

Гарантируется, что суммарная длина десятичных записей всех $n$ во входных данных не превосходит $5\,000\,000$.

Выходные данные

Для каждого тестового случая выведите целое число без ведущих нулей, обозначающее наибольшее почти число Bobo, строго меньшее $n$. Если такого целого числа нет, вместо него выведите $-1$.

Примеры

Входные данные 1

12345
67890
11111
1000
26782641

Выходные данные 1

12212
67767
11010
-1
26777267