Gitt en binærstreng $s$ med lengde $n$ ($01$-streng). Du må erstatte ett tegn i $s[2 \ldots n - 1]$ med $\oplus$, slik at den endelige verdien til uttrykket blir så stor som mulig.

$\oplus$ representerer den binære XOR-operasjonen. Etter erstatningen behandles begge sider av $\oplus$ som binære tall.

Inndata

Ett enkelt testtilfelle inneholder flere datasett.

Den første linjen i inndataene er antall datasett $T$ ($1 \le T \le 10^5$), som representerer antall datasett i dette testtilfellet.

For hvert datasett er det én linje som inneholder en binærstreng $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Det er garantert at i ett enkelt testtilfelle er $\sum |s| \le 5 \cdot 10^5$.

Utdata

For hvert datasett skal du skrive ut én linje som inneholder en binærstreng som representerer det største resultatet på binær form (tallstrengen kan ikke inneholde ledende $0$-er, bortsett fra det enslige sifferet $0$).

Eksempler

Inndata 1

5
010
0110
1000
10101
01000

Utdata 1

0
10
10
100
10