Annettuna on pituutta $n$ oleva binäärimerkkijono $s$ ($01$-merkkijono). Sinun tulee korvata yksi merkki välillä $s[2 \ldots n - 1]$ merkillä $\oplus$ siten, että lausekkeen lopullinen arvo on mahdollisimman suuri.

$\oplus$ tarkoittaa binääristä XOR-operaatiota. Korvaamisen jälkeen merkin $\oplus$ molempia puolia käsitellään binäärilukuina.

Syöte

Yksi testitapaus sisältää useita tietoaineistoja.

Syötteen ensimmäinen rivi on tietoaineistojen lukumäärä $T$ ($1 \le T \le 10^5$), joka ilmaisee tietoaineistojen määrän tässä testitapauksessa.

Jokaista tietoaineistoa kohden on yksi rivi, joka sisältää binäärimerkkijonon $s$ ($3 \le |s| \le 5 \cdot 10^5$).

On taattu, että yhdessä testitapauksessa $\sum |s| \le 5 \cdot 10^5$.

Tuloste

Tulosta jokaista tietoaineistoa kohden yksi rivi, joka sisältää binäärimuodossa suurinta mahdollista tulosta kuvaavan binäärimerkkijonon (lukumerkkijonossa ei saa olla etunollia $0$ lukuun ottamatta yksittäistä numeroa $0$).

Esimerkit

Syöte 1

5
010
0110
1000
10101
01000

Tuloste 1

0
10
10
100
10