Gegeben ist eine Binärzeichenkette $s$ der Länge $n$ ($01$-Zeichenkette). Du musst ein Zeichen in $s[2 \ldots n - 1]$ durch $\oplus$ ersetzen, sodass der Endwert des Ausdrucks so groß wie möglich wird.

$\oplus$ steht für die binäre XOR-Operation. Nach der Ersetzung werden beide Seiten von $\oplus$ als Binärzahlen aufgefasst.

Eingabe

Ein einzelner Testfall enthält mehrere Datensätze.

Die erste Zeile der Eingabe ist die Anzahl der Datensätze $T$ ($1 \le T \le 10^5$), die die Anzahl der Datensätze in diesem Testfall angibt.

Für jeden Datensatz gibt es eine Zeile mit einer Binärzeichenkette $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Es wird garantiert, dass in einem einzelnen Testfall $\sum |s| \le 5 \cdot 10^5$ gilt.

Ausgabe

Gib für jeden Datensatz eine Zeile mit einer Binärzeichenkette aus, die das größte Ergebnis in Binärdarstellung angibt (die Zahlenzeichenkette darf außer bei der einzelnen Ziffer $0$ keine führenden $0$-en enthalten).

Beispiele

Eingabe 1

5
010
0110
1000
10101
01000

Ausgabe 1

0
10
10
100
10