题目描述

苗苗正在整理一串二进制记录。记录可以看作一个长度至少为 $3$ 的 01 字符串 $s$。

苗苗需要选择一个既不是第一个字符、也不是最后一个字符的位置，把这一位替换成符号 $xor$。替换之后，符号左边和右边分别被看作二进制整数，苗苗会计算这两个整数的按位异或结果。

苗苗想知道，这个结果最大可以是多少。请你输出最大结果的二进制表示。

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

输入格式

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

接下来 $T$ 行，每行一个长度至少为 $3$ 的 01 字符串 $s$。

输出格式

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

8
010
0110
1000
10101
01000
01010
010110
00000

0
10
10
100
10
11
111
0

数据规模

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

对于全部数据，满足 $1 \le T \le 10^5$，$3 \le n$，$s$ 仅由字符 0 和 1 组成，所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。

特殊性质 A：保证所有字符串均以字符 1 开头。 特殊性质 B：保证所有字符串均以字符 0 开头。