給定一個長度為 $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