给定一个长度为 $n$ 的二进制字符串 $s$（01 字符串）。你需要将 $s[2 \dots 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