Dada una cadena binaria $s$ de longitud $n$ (cadena $01$). Debes reemplazar un carácter en $s[2 \ldots n - 1]$ por $\oplus$, de modo que el valor final de la expresión sea lo más grande posible.

$\oplus$ representa la operación XOR binaria. Después del reemplazo, ambos lados de $\oplus$ se tratan como números binarios.

Entrada

Un solo caso de prueba contiene múltiples conjuntos de datos.

La primera línea de la entrada es el número de conjuntos de datos $T$ ($1 \le T \le 10^5$), que representa el número de conjuntos de datos en este caso de prueba.

Para cada conjunto de datos, hay una línea que contiene una cadena binaria $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Se garantiza que en un solo caso de prueba, $\sum |s| \le 5 \cdot 10^5$.

Salida

Para cada conjunto de datos, imprime una línea que contenga una cadena binaria que represente el mayor resultado en forma binaria (la cadena numérica no puede contener $0$s a la izquierda, excepto para el dígito único $0$).

Ejemplos

Entrada 1

5
010
0110
1000
10101
01000

Salida 1

0
10
10
100
10