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


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


-----Example-----
Input
4
00
01
111
110

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

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if s.count('1') == n or s.count('1') == 0:
		print(s)
	else:
		odp = [0,1]*n
		for i in range(n):
			if i < n-1:
				print("01", end = "")
			else:
				print("01")

n = int(input())
for i in range(n):
    c = input()
    if "0" in c and "1" in c:
        print("01"*len(c))
    else:
        print(c)


T = int(input())
for _ in range(T):
    s = input()
    if s.count("0") == 0 or s.count("1") == 0:
        print(s)
    else:
        print("01" * len(s))


for _ in range(int(input())):
    s = input()
    if len(s) in {s.count('0'), s.count('1')}:
        print(s)
    else:
        print('01' * len(s))


for t in range(int(input())):
    a = list(input())
    if len(set(a)) == 1:
        print(a[0]*len(a))
    else:
        print('01'*len(a))

from math import inf
t = int(input())
for q in range(t):
    tt = input()
    s = "01" * len(tt)
    one = False
    zero = False
    for i in tt:
        if i == '0':
            zero = True
        else:
            one = True
    if not one or not zero:
        print(tt)
    else:
        print(s)


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    a = input()
    n = len(a)
    one = 0
    for c in a:
        if c == '1':
            one += 1
    if one == 0 or one == n:
        print(a)
    else:
        print(''.join(['01' for i in range(n)]))


n = int(input())
for _ in range(n):
    s = input()
    p = len(s)
    if all(c == s[0] for c in s):
        print(s)
    else:
        print('01' * p)

from math import *

for zz in range(int(input())):
    t = [int(i) for i in input()]
    n = len(t)
    if sum(t) == 0:
        print(*[0] * n, sep='')
    elif sum(t) == n:
        print(*[1] * n, sep='')
    else:
        print(*[0, 1] * (n), sep='')