נתונה מחרוזת בינארית $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