题目描述

假设有一个字符串$s$，如果它的第$i$ 个字符和第$i+k$ 个字符相等$(1\le i\le|s|-k)$ ，那么这个字符串的周期为$k$ 。其中，$|s|$ 表示字符串$s$ 的长度。

现在给你一个字符串$t$ ，$t$ 内只包括0和1，请你找出这个$s$ ，使其满足如下条件：

1. 字符串$s$ 也只包括0和1。
2. $|s|\le 2\times|t|$（$s$ 的长度不能超过$t$ 的长度的两倍）。
3. $t$ 是$s$ 的子串。
4. 在满足上面3个条件的情况下，$s$ 需要有最小的周期$k$ 。

$t$ 是$s$ 的子串就是说当$s$ 删除$0$个或更多个字符后（不能改变顺序），$s$ 就变成了$t$ 。例如011就是10101的子串。

输入格式

第一行是一个正整数$T$，表示数据的组数。

接下来$T$行，每行有一个只包含0和1的字符串$t$ $(1\le|t|\le100)$。

输出格式

如果有多种解，输出一个符合条件的字符串$s$ 即可。

样例

4
00
01
111
110

00
01
11111
1010