Binary Period
Description
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:
- String $s$ consists only of 0's and 1's;
- The length of $s$ doesn't exceed $2 \cdot |t|$;
- String $t$ is a subsequence of string $s$;
- 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.
Input
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.
Output
Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them.
Samples
4
00
01
111
110
00
01
11111
1010
Note
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$.