俾定一個長度為 $n$ 嘅二進制字串 $s$（$01$ 字串）。你需要將 $s[2 \ldots n - 1]$ 入面嘅一個字元替換為 $\oplus$，令表達式嘅最終值盡可能大。
$\oplus$ 代表二進制異或（XOR）運算。替換之後，$\oplus$ 兩邊嘅部分都會被當作二進制數處理。
輸入格式
單一個測試點包含多組測試數據。
輸入嘅第一行係測試數據嘅組數 $T$ ($1 \le T \le 10^5$)，代表呢個測試點入面嘅測試數據組數。
對於每組測試數據，包含一行一個二進制字串 $s$ ($3 \le |s| \le 5 \cdot 10^5$)。
保證喺單一個測試點入面，$\sum |s| \le 5 \cdot 10^5$。
輸出格式
對於每組測試數據，輸出一行包含一個二進制字串，代表二進制形式下嘅最大結果（除咗單個數字 $0$ 之外，個數字字串唔可以包含前導 $0$）。
範例
輸入格式 1
5 010 0110 1000 10101 01000
輸出格式 1
0 10 10 100 10