จำนวนเต็มบวกเรียกว่า จำนวน Bobo หากรูปแทนฐานสิบของมันได้จากการนำจำนวนเต็มเดียวกันสองชุดมาต่อกัน ตัวอย่างเช่น $12341234$ และ $3232$ เป็นจำนวน Bobo แต่ $1234321$ และ $1322$ ไม่ใช่

จำนวนเต็มบวกเรียกว่า จำนวนเกือบ Bobo หากหลังจากรวมกลุ่มเลขโดดที่เหมือนกันและอยู่ติดกันทั้งหมดแล้ว จำนวนที่ได้เป็นจำนวน Bobo ตัวอย่างเช่น $1112223112233$ กลายเป็น $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