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".

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.

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$.

Samples

4
00
01
111
110

00
01
11111
1010