Data una stringa binaria $s$ di lunghezza $n$ (stringa $01$), devi sostituire un carattere in $s[2 \ldots n - 1]$ con $\oplus$, in modo che il valore finale dell'espressione sia il più grande possibile.

$\oplus$ rappresenta l'operazione XOR binaria. Dopo la sostituzione, entrambi i lati di $\oplus$ vengono trattati come numeri binari.

Input

Un singolo caso di test contiene più set di dati.

La prima riga dell'input è il numero di set di dati $T$ ($1 \le T \le 10^5$), che rappresenta il numero di set di dati in questo caso di test.

Per ogni set di dati, c'è una riga contenente una stringa binaria $s$ ($3 \le |s| \le 5 \cdot 10^5$).

È garantito che in un singolo caso di test $\sum |s| \le 5 \cdot 10^5$.

Output

Per ogni set di dati, stampa una riga contenente una stringa binaria che rappresenta il risultato massimo in forma binaria (la stringa numerica non può contenere $0$ iniziali, tranne nel caso della singola cifra $0$).

Esempi

Input 1

5
010
0110
1000
10101
01000

Output 1

0
10
10
100
10