Sebuah bilangan bulat positif disebut bilangan bobo jika representasi desimalnya dapat diperoleh dengan menggabungkan dua salinan bilangan bulat yang sama. Sebagai contoh, $12341234$ dan $3232$ adalah bilangan bobo, sedangkan $1234321$ dan $1322$ bukan.

Sebuah bilangan bulat positif disebut bilangan hampir bobo jika, setelah semua digit sama yang berurutan digabungkan, bilangan yang dihasilkan adalah bilangan bobo. Sebagai contoh, $1112223112233$ menjadi $123123$ setelah semua digit sama yang berurutan digabungkan, sehingga merupakan bilangan hampir bobo.

Bobo memiliki bilangan $n$ yang sangat besar, dan ingin mengetahui bilangan hampir bobo terbesar yang lebih kecil daripada $n$.

Masukan

Masukan memuat nol atau lebih kasus uji, dan diakhiri oleh akhir berkas. Untuk setiap kasus uji:

Baris pertama memuat sebuah bilangan bulat $n$ tanpa nol di depan ($1\le n\le 10^{5\,000\,000}$).

Dijamin bahwa total panjang representasi desimal semua $n$ dalam masukan tidak melebihi $5\,000\,000$.

Keluaran

Untuk setiap kasus uji, cetak sebuah bilangan bulat tanpa nol di depan yang menyatakan bilangan hampir bobo terbesar yang benar-benar lebih kecil daripada $n$. Jika tidak ada bilangan bulat semacam itu, cetak $-1$ sebagai gantinya.

Contoh

Masukan 1

12345
67890
11111
1000
26782641

Keluaran 1

12212
67767
11010
-1
26777267