Problem: 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 ⋅ |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 ≤ T ≤ 100) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains string t (1 ≤ |t| ≤ 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.

Solution (in PYTHON3):

Solution:
'''Oh, yeah

I just pretend that I'm in the dark

I don't regret 'cause my heart can't take a loss

I'd rather be so oblivious

I'd rather be with you

When it's said, when it's done, yeah

I don't ever wanna know

I can tell what you done, yeah

When I look at you

In your eyes

I see there's something burning inside you

Oh, inside you

In your eyes

I know it hurts to smile but you try to

Oh, you try to

You always try to hide the pain

You always know just what to say

I always look the other way

I'm blind, I'm blind

In your eyes, you lie, but I don't let it define you

Oh, define you

I tried to find love

In someone else too many times

But I hope you know I mean it (mean it)

When I tell you you're the one that was on my mind, oh

When it's said, when it's done, yeah

I would never let you know (let you know)

I'm ashamed of what I've done, yeah

When I look at you

In your eyes (your eyes)

I see there's something burning inside you (inside you)

Oh, inside you (oh, inside you)

In your eyes

I know it hurts to smile but you try to (but you try to)

Oh, you try to (I try to)

You always try to hide the pain (oh, oh)

You always know just what to say (oh, dear)

I always look the other way

I'm blind, I'm blind

In your eyes, you lie, but I don't let it define you (hey)

Oh, define you

In your eyes

I see there's something burning inside you

Oh, inside you

You always try to hide the pain

You always know just what to say

I always look the other way

I'm blind, I'm blind

In your eyes, you lie, but I don't let it define you

Oh, define you '''
#General library for finding nCr modulo m
#where m, n, r can be any integer without any limits
#For usge just call the function ncr(n, r, m)

def factorise(m):
	ans = []
	p = 2
	while(m != 1):
		if (m%p != 0):
			p += 1
			continue
		e = 0
		while(m % p == 0) :
			m //= p
			e += 1
		ans.append([p, e])
		p += 1
	return ans

def mulmod(a, b, c):
	res = a * b
	if (res >= c):
		res %= c
	return res

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while(n > 0):
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x

def expo(a, b):
	x = 1
	y = a
	while(b > 0):
		if (b&1):
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, c):
	x = 1
	y = a
	while(b > 0):
		if (b&1):
			x = mulmod(x, y, c)
		y = mulmod(y, y, c)
		b >>= 1
	return x

def init(p, pk):
	fact = []
	fact.append(1)
	for i in range(1, pk):
		red = i
		if (red % p == 0):
			red = 1
		fact.append(mulmod(fact[i-1], red, pk))
	return fact

def fact_mod(n, p, pk, fact):
	res = 1
	while(n > 0):
		times = n//pk
		res = mulmod(res, power(fact[pk-1], times, pk), pk)
		res = mulmod(res, fact[n%pk], pk)
		n //= p
	return res

def count_fact(n, p):
	ans = 0
	while(n > 0):
		ans += n//p
		n //= p
	return ans

def ncr_pk(n, r, p, e):
	if (r > n or r < 0):
		return 0
	if (r == 0 or n == r):
		return 1
	_e = count_fact(n, p) - count_fact(r, p) - count_fact(n-r, p)
	assert(_e >= 0)
	if (_e >= e):
		return 0
	pk = expo(p, e)
	fact = init(p, pk)
	ans = fact_mod(n, p, pk, fact)
	ans = mulmod(ans, mod_inverse(fact_mod(r, p, pk, fact), pk), pk)
	ans = mulmod(ans, mod_inverse(fact_mod(n-r, p, pk, fact), pk), pk)
	ans = mulmod(ans, expo(p, _e), pk)
	return ans

def pre_process(rem, mods):
	crt = []
	a = 1
	b = 1
	m = mods[0]
	crt.append([mods[0], a, b])
	L =	len(mods)
	for i in range(1, L):
		a = mod_inverse(m, mods[i])
		b = mod_inverse(mods[i], m)
		crt.append([m, a, b])
		m *= mods[i]
	assert(len(crt) == len(mods))
	return crt

def find_crt(rem, mods, crt):
	assert(len(crt) == len(mods))
	ans = rem[0]
	m = crt[0][0]
	L = len(mods)
	for i in range(1, L):
		a = crt[i][1]
		b = crt[i][2]
		m = crt[i][0]
		_m = m * mods[i]
		ans = mulmod(ans, b * mods[i], _m)
		ans = (ans + mulmod(rem[i], a * m, _m)) % (_m)
	return ans

def ncr(n, r, m):
	pf = factorise(m)
	rem = []
	mods = []
	L = len(pf)
	for i in range(L):
		get = ncr_pk(n, r, pf[i][0], pf[i][1])
		rem.append(get)
		mods.append(expo(pf[i][0], pf[i][1]))
	crt = pre_process(rem, mods)
	ans = find_crt(rem, mods, crt)
	return ans

  #returns (a + b) mod c
def add(a,b,c):
	res=a+b
	if(res>=c):
		return res-c
	else:
		return res

#returns (a * b) mod c
def mod(a,b,c):
	res=a*b
	if(res>=c):
		return res%c
	else:
		return res

#Complexity: O(max(log2(a), log2(b)))
def gcd(a,b):
	while b:
		a,b=b,a%b
	return a

#Complexity: O(max(log2(a), log2(b)))
def lcm(a,b):
	w=a//gcd(a,b)
	return w*b

#returns a^b
#Complexity: O(log2(b))
def expo(a,b):
	x,y=1,a
	while(b>0):
		if(b&1):
			x=x*y
		y=y*y
		b>>=1
	return x

#return (a ^ b) mod m
#Complexity: O(log2(b))
def power(a,b,m):
	x,y=1,
	while(b>0):
		if(b&1):
			x=mod(x,y,m)
		y=mod(y,y,m)
		b>>=1
	return x

#returns (a ^ (-1)) mod m
#worlemon only for m = prime
#Complexity: O(log2(m))
def inv(a,m):
	return power(a,m-2,m)

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while(n > 0):
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x

import random
from queue import Queue

def gcd(a,b):
	while b:
		a,b=b,a%b
	return a

def expo(a,b):
	x,y=1,a
	while(b>0):
		if(b&1):
			x=x*y
		y=y*y
		b>>=1
	return x

primes=[0]*100000

def sieve():
	primes[1]=1
	primes[2]=2
	j=4
	while(j<100000):
		primes[j]=2
		j+=2
	j=3
	while(j<100000):
		if primes[j]==0:
			primes[j]=j
			i=j*j
			k=j<<1
			while(i<100000):
				primes[i]=j
				i+=k
		j+=2

#checlemon if p is prime or not
def rabin_miller(p):
	if(p<100000):
		return primes[p]==p
	if(p%2==0):
		return False
	s=p-1
	while(s%2==0):
		s>>=1
	for i in range(5):
		a=random.randrange(p-1)+1
		temp=s
		mod=pow(a,temp,p)
		while(temp!=p-1 and mod!=1 and mod!=p-1):
			mod=(mod*mod)%p
			temp=temp*2
		if(mod!=p-1 and temp%2==0):
			return False
	return True

#returns a prime factor of N
def brent(N):
	if(N%2==0):
		return 2
	if(N<100000):
		return primes[N]
	y,c,m = random.randint(1, N-1),random.randint(1, N-1),random.randint(1, N-1)
	g,r,q = 1,1,1
	while g==1:
		x=y
		for i in range(r):
			y=((y*y)%N+c)%N
		k=0
		while(k<r and g==1):
			ys=y
			for i in range(min(m,r-k)):
				y=((y*y)%N+c)%N
				q=q*(abs(x-y))%N
			g=gcd(q,N)
			k=k+m
		r=r*2
	if g==N:
		while True:
			ys=((ys*ys)%N+c)%N
			g=gcd(abs(x-ys),N)
			if g>1:
				break
	return g

def factorise(n):
	Q_1=Queue()
	Q_2=[]
	Q_1.put(n)
	while(not Q_1.empty()):
		l=Q_1.get()
		if(rabin_miller(l)):
			Q_2.append(l)
			continue
		d=brent(l)
		if(d==l):
			Q_1.put(l)
		else:
			Q_1.put(d)
			Q_1.put(l//d)
	return Q_2


def sieve():
  t=int(input())
  for _ in range(t):
	  n=int(input())
	  L=factorise(n)
	  L.sort()
	  i=0
	  while(i<len(L)):
		  cnt=L.count(L[i])
		  print ("%s^%s"%(L[i],cnt)),
		  i+=cnt
	  print

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while(n > 0):
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x

#prime sieve where prime[i] stores a prime factor of i

primes=[0]*1000000

#Complexity: O(n * log2(log2(n)))
def sieve():
	primes[1]=1
	primes[2]=2
	j=4
	while(j<1000000):
		primes[j]=2
		j+=2
	j=3
	while(j<1000000):
		if primes[j]==0:
			primes[j]=j
			i=j*j
			k=j<<1
			while(i<1000000):
				primes[i]=j
				i+=k
		j+=2

# It uses 64-bit fft and is ekadsremely fast
# almost comparable to C++ codes.
# For usage just call poly_mul with the polynomials.

from random import *
import time

def ilog2(n):
	return 0 if n <= 0 else n.bit_length() - 1

def pack(pack, shamt):
	size = len(pack)
	while size > 1:
		npack = []
		for i in range(0, size - 1, 2):
			npack += [pack[i] | (pack[i+1] << shamt)]
		if size & 1:
			npack += [pack[-1]]
		pack, size, shamt = npack, (size + 1) >> 1, shamt << 1
	return pack[0]

def unpack(M, size, shamt):
	s, sizes = size, []
	while s > 1:
		sizes += [s]
		s = (s + 1) >> 1
	ret = [M]
	for size in sizes[::-1]:
		mask, nret = (1 << shamt) - 1, []
		for c in ret:
			nret += [c & mask, c >> shamt]
		ret, shamt = nret[:size], shamt >> 1
	return ret

def poly_mul(f, g, mod = 1000000007):
	size = min(len(f), len(g))
	shift = ((mod - 1) ** 2 * size).bit_length()
	rsize = len(f) + len(g) - 1
	h = unpack(pack(f, shift) * pack(g, shift), rsize, shift * (1 << ilog2(rsize - 1)))
	return [int(x % mod) for x in h]
############################################################################################################################################
for _ in range(int(input())):
    s=input()
    if len(set(s))==1:
        print(s)
        continue
    a=""
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            if s[i]=='1':
                a+='1'+'0'
            else:
                a+='0'+'1'
        else:
            a+=s[i]
    a+=s[len(s)-1]
    print(a)



##############################################################################################################################################