أُعطيت سلسلة ثنائية $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