On vous donne une chaîne binaire $s$ de longueur $n$ (chaîne $01$). Vous devez remplacer un caractère dans $s[2 \ldots n - 1]$ par $\oplus$, de sorte que la valeur finale de l'expression soit la plus grande possible.

$\oplus$ représente l'opération XOR binaire. Après le remplacement, les deux côtés de $\oplus$ sont traités comme des nombres binaires.

Entrée

Un même fichier de test contient plusieurs jeux de données.

La première ligne de l'entrée est le nombre de jeux de données $T$ ($1 \le T \le 10^5$), représentant le nombre de jeux de données dans ce test.

Pour chaque jeu de données, il y a une ligne contenant une chaîne binaire $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Il est garanti que dans un même test, $\sum |s| \le 5 \cdot 10^5$.

Sortie

Pour chaque jeu de données, affichez une ligne contenant une chaîne binaire qui représente le plus grand résultat sous forme binaire (la chaîne numérique ne peut pas contenir de $0$ non significatifs en tête, sauf pour le chiffre unique $0$).

Exemples

Entrée 1

5
010
0110
1000
10101
01000

Sortie 1

0
10
10
100
10