Gefinn er tvíundastrengur $s$ af lengd $n$ ($01$-strengur). Þú þarft að skipta einum staf í $s[2 \ldots n - 1]$ út fyrir $\oplus$, þannig að lokagildi segðarinnar verði eins stórt og mögulegt er.

$\oplus$ táknar tvíunda XOR-aðgerðina. Eftir útskiptinguna eru báðar hliðar $\oplus$ meðhöndlaðar sem tvíundatölur.

Inntak

Eitt prófunartilvik inniheldur mörg gagnasett.

Fyrsta línan í inntakinu er fjöldi gagnasetta $T$ ($1 \le T \le 10^5$), sem táknar fjölda gagnasetta í þessu prófunartilviki.

Fyrir hvert gagnasett er ein lína sem inniheldur tvíundastreng $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Tryggt er að í einu prófunartilviki gildir $\sum |s| \le 5 \cdot 10^5$.

Úttak

Fyrir hvert gagnasett skal prenta eina línu sem inniheldur tvíundastreng sem táknar stærstu niðurstöðuna á tvíundaformi (talnastrengurinn má ekki innihalda fremstu $0$-ur nema fyrir staka tölustafinn $0$).

Dæmi

Inntak 1

5
010
0110
1000
10101
01000

Úttak 1

0
10
10
100
10