長さ $n$ のバイナリ文字列 $s$（$01$ 文字列）が与えられます。式の最終的な値ができるだけ大きくなるように、$s[2 \ldots n - 1]$ のうちの 1 文字を $\oplus$ に置き換える必要があります。

$\oplus$ は二進の排他的論理和（XOR）演算を表します。置き換え後、$\oplus$ の両側はどちらも二進数として扱われます。

入力

1 つのテストケースには複数のデータセットが含まれます。

入力の最初の行はデータセットの数 $T$ ($1 \le T \le 10^5$) であり、このテストケースにおけるデータセットの数を表します。

各データセットについて、バイナリ文字列 $s$ ($3 \le |s| \le 5 \cdot 10^5$) を含む 1 行が与えられます。

1 つのテストケースにおいて、$\sum |s| \le 5 \cdot 10^5$ であることが保証されています。

出力

各データセットについて、最大の結果を二進表記で表すバイナリ文字列を 1 行に出力してください（単一の数字 $0$ を除き、先頭に余分な $0$ を含めてはなりません）。

入出力例

入力 1

5
010
0110
1000
10101
01000

出力 1

0
10
10
100
10