Diberikan sebuah string biner $s$ dengan panjang $n$ (string $01$). Anda perlu mengganti satu karakter pada $s[2 \ldots n - 1]$ dengan $\oplus$, sedemikian sehingga nilai akhir dari ekspresi tersebut sebesar mungkin.

$\oplus$ menyatakan operasi XOR biner. Setelah penggantian, kedua sisi dari $\oplus$ diperlakukan sebagai bilangan biner.

Masukan

Satu kasus uji terdiri atas beberapa set data.

Baris pertama masukan adalah banyaknya set data $T$ ($1 \le T \le 10^5$), yang menyatakan banyaknya set data dalam kasus uji ini.

Untuk setiap set data, terdapat satu baris yang berisi sebuah string biner $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Dijamin bahwa dalam satu kasus uji, $\sum |s| \le 5 \cdot 10^5$.

Keluaran

Untuk setiap set data, keluarkan satu baris yang berisi sebuah string biner yang menyatakan hasil terbesar dalam bentuk biner (string bilangan tidak boleh memiliki angka $0$ di depan kecuali untuk satu digit $0$).

Contoh

Masukan 1

5
010
0110
1000
10101
01000

Keluaran 1

0
10
10
100
10