กำหนดสตริงฐานสอง $s$ ความยาว $n$ (สตริง $01$) คุณต้องแทนที่อักขระหนึ่งตัวใน $s[2 \ldots n - 1]$ ด้วย $\oplus$ เพื่อให้ค่าสุดท้ายของนิพจน์มีค่ามากที่สุดเท่าที่จะเป็นไปได้

$\oplus$ แทนการดำเนินการ XOR ฐานสอง หลังจากแทนที่แล้ว ทั้งสองข้างของ $\oplus$ จะถูกมองว่าเป็นเลขฐานสอง

ข้อมูลนำเข้า

กรณีทดสอบหนึ่งชุดประกอบด้วยข้อมูลหลายชุด

บรรทัดแรกของข้อมูลนำเข้าคือจำนวนชุดข้อมูล $T$ ($1 \le T \le 10^5$) แทนจำนวนชุดข้อมูลในกรณีทดสอบนี้

สำหรับแต่ละชุดข้อมูล จะมีหนึ่งบรรทัดที่ประกอบด้วยสตริงฐานสอง $s$ ($3 \le |s| \le 5 \cdot 10^5$)

รับประกันว่าในกรณีทดสอบเดียว $\sum |s| \le 5 \cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูล ให้พิมพ์หนึ่งบรรทัดที่ประกอบด้วยสตริงฐานสองซึ่งแทนผลลัพธ์ที่มากที่สุดในรูปฐานสอง (สตริงตัวเลขต้องไม่มีเลข $0$ นำหน้า ยกเว้นกรณีที่เป็นเลขโดด $0$ เพียงตัวเดียว)

ตัวอย่าง

ข้อมูลนำเข้า 1

5
010
0110
1000
10101
01000

ข้อมูลส่งออก 1

0
10
10
100
10