替换（replace）

题目描述

苗苗正在整理一串二进制记录。记录只由字符 0 和 1 组成。

现在苗苗需要选择一个既不是开头、也不是结尾的位置，把这一位替换成异或符号 ⊕。替换之后，符号左边和右边都会被看作二进制整数，苗苗会计算这两个整数的按位异或结果。

苗苗希望让这个结果尽可能大。请你输出最大结果的二进制表示。

注意，输出不能含有前导零；如果最大结果为 $0$，请输出 0。

输入格式

从文件 replace.in 中读入数据。

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行一个长度至少为 $3$ 的二进制串 $s$。

输出格式

输出到文件 replace.out 中。

对于每组测试数据，输出一行一个二进制串，表示最大结果。

输入输出样例 #1

输入 #1

8
010
0110
1000
10101
01000
01010
010110
00000

输出 #1

0
10
10
100
10
11
111
0

说明/提示

对于样例中的 10101，可以把第 $2$ 位、第 $3$ 位或第 $4$ 位替换成 ⊕：

• 1 ⊕ 101 = 100；
• 10 ⊕ 01 = 11；
• 101 ⊕ 1 = 100。

因此最大结果为 100。

设每组测试数据中字符串 $s$ 的长度为 $n$。

对于全部数据，满足：

• $1\le T\le 10^5$；
• $3\le n$；
• $s$ 仅由字符 0 和 1 组成；
• 所有测试数据中 $n$ 的总和不超过 $5\times 10^5$。

样例文件