Dany jest napis binarny $s$ o długości $n$ (napis $01$). Musisz zastąpić jeden znak we fragmencie $s[2 \ldots n - 1]$ symbolem $\oplus$ tak, aby końcowa wartość wyrażenia była jak największa.

$\oplus$ oznacza binarną operację XOR. Po zastąpieniu obie strony symbolu $\oplus$ są traktowane jako liczby zapisane w systemie dwójkowym.

Wejście

Pojedynczy przypadek testowy zawiera wiele zestawów danych.

Pierwszy wiersz wejścia to liczba zestawów danych $T$ ($1 \le T \le 10^5$), oznaczająca liczbę zestawów danych w tym przypadku testowym.

Dla każdego zestawu danych podany jest jeden wiersz zawierający napis binarny $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Gwarantowane jest, że w pojedynczym przypadku testowym $\sum |s| \le 5 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wypisz jeden wiersz zawierający napis binarny oznaczający największy wynik w postaci binarnej (napis reprezentujący liczbę nie może zawierać wiodących cyfr $0$, z wyjątkiem pojedynczej cyfry $0$).

Przykład

Wejście 1

5
010
0110
1000
10101
01000

Wyjście 1

0
10
10
100
10