假设字符串 $$$s$$$ 有句点 $$$k$$$,如果 $$$s_i = s_{i + k}$$$ 对于从 $$$1$$$ 到 $$$|s| 的所有 $$$i$$$ - k$$$($$$|s|$$$ 表示字符串 $$$s$$$ 的长度),$$$k$$$ 是具有此属性的最小正整数。
一些周期示例:对于 $$$s$$$="0101",周期为 $$$k=2$$$,对于 $$$s$$$="0000",周期为 $$$k=1$$$,对于 $$$s$$$="010",周期为 $$$k=2$$$,对于 $$$s$$$="0011",周期为$$$k=4$$$。
给定字符串 $$$t$$$ 仅由 0 和 1 组成,你需要找到这样的字符串 $$$s$$$ :
1. 字符串$$$s$$$仅由0和1组成;
2、$$$s$$$的长度不超过$$$2 \cdot |t|$$$;
3. 字符串$$$t$$$是字符串$$$s$$$的子序列;
4. 字符串 $$$s$$$ 在满足条件 1—3 的所有字符串中具有最小的可能周期。
让我们回想一下,$$$t$$$ 是 $$$s$$$ 的子序列,如果 $$$t$$$ 可以通过删除零个或多个元素(任意)从 $$$s$$$ 导出,而不改变剩余元素的顺序。例如,$$$t$$$="011" 是 $$$s$$$="10101" 的子序列。
输入
第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 测试用例的数量。
接下来的 $$$T$$$ 行包含测试用例 - 每行一个。每行包含仅由 0 和 1 组成的字符串 $$$t$$$ ($$$1 \le |t| \le 100$$$)。
输出
为每个测试用例打印一个字符串 - 您需要查找的字符串 $$$s$$$。如果有多个解决方案,请打印其中之一。
示例
输入 #1
4 00 01 111 110
输出 #1
00 01 11111 1010
注意
在第一个和第二个测试用例中,$$$s = t$$$ 因为它已经是最佳解决方案之一。答案的句点分别等于 $$$1$$$ 和 $$$2$$$。
在第三个测试用例中,有更短的最佳解决方案,但没关系,因为我们不需要最小化字符串 $$$s$$$。字符串 $$$s$$$ 的句点等于 $$$1$$$。