Givet en binär sträng $s$ av längd $n$ ($01$-sträng). Du ska ersätta ett tecken i $s[2 \ldots n - 1]$ med $\oplus$, så att uttryckets slutliga värde blir så stort som möjligt.

$\oplus$ representerar den binära XOR-operationen. Efter ersättningen betraktas båda sidorna om $\oplus$ som binära tal.

Indata

Ett enskilt testfall innehåller flera datamängder.

Den första raden i indatan är antalet datamängder $T$ ($1 \le T \le 10^5$), som representerar antalet datamängder i detta testfall.

För varje datamängd finns en rad som innehåller en binär sträng $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Det garanteras att i ett enskilt testfall gäller $\sum |s| \le 5 \cdot 10^5$.

Utdata

För varje datamängd, skriv ut en rad som innehåller en binär sträng som representerar det största resultatet i binär form (talsträngen får inte innehålla inledande $0$:or förutom för den ensamma siffran $0$).

Exempel

Indata 1

5
010
0110
1000
10101
01000

Utdata 1

0
10
10
100
10