Ұзындығы $n$ болатын екілік жол $s$ ($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