A13418. Binary Period

Let's say string $s$ has period $k$ if $s_i = s_{i + k}$ for all $i$ from $1$ to $|s| - k$ ( $|s|$ means length of string $s$ ) and $k$ is the minimum positive integer with this property.

Some examples of a period: for $s$ ="0101" the period is $k=2$ , for $s$ ="0000" the period is $k=1$ , for $s$ ="010" the period is $k=2$ , for $s$ ="0011" the period is $k=4$ .

You are given string $t$ consisting only of 0's and 1's and you need to find such string $s$ that:

1. String $s$ consists only of 0's and 1's;
2. The length of $s$ doesn't exceed $2 \cdot |t|$ ;
3. String $t$ is a subsequence of string $s$ ;
4. String $s$ has smallest possible period among all strings that meet conditions 1—3.

Let us recall that $t$ is a subsequence of $s$ if $t$ can be derived from $s$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $t$ ="011" is a subsequence of $s$ ="10101".

The first line contains single integer $T$ ( $1 \le T \le 100$ ) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains string $t$ ( $1 \le |t| \le 100$ ) consisting only of 0's and 1's.

Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them.

In the first and second test cases, $s = t$ since it's already one of the optimal solutions. Answers have periods equal to $1$ and $2$ , respectively.

In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $s$ . String $s$ has period equal to $1$ .