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:
# s1=list(map(int,input().split()))		


# t = int(input())

# for _ in range(t):
# 	n = int(input())
# 	# s1=list(map(int,input().split()))
# 	s1 = input()
# 	s1 = str(s1)	

# 	temp = 0

# 	a=[]
# 	b=[]

# 	for i in range(n):
# 		if s1[i]=='0':
# 			a.append(0)
# 			b.append(0)
# 		elif s1[i]=='2':
# 			a.append(1)
# 			b.append(1)
# 		else:
# 			if(temp==0):
# 				a.append(1)
# 				b.append(0)
# 				temp = 1
# 			else:
# 				a.append(0)
# 				b.append(1)
# 				temp = 0
						


	
# 	print(a)
# 	print(b)					


# print(0)



# A = [1,2,3,4,5,5]

# m1 = -1000
# m2 = -1000
# temp = 0
# for i in A:
#     if temp>=0:
#         print(i)
#         temp = temp+i
#         print(temp)
#         if(temp>m2):
#             m2 = temp
#     else:
#         temp = i
		

# print(m2)       



# def reverse_Bits(n):
#   result = 0
#   for i in range(32):
#       result <<= 1
#       result |= n & 1
#       n >>= 1
#   return result
			
# print(reverse_Bits(1234))




# inp = input()


# print(inp)

# l = len(inp)
# get_bin = lambda x, n: format(x, 'b').zfill(n)

# for i in inp:
#   temp = get_bin(int(i), 32)
#   print(reverse_Bits(10)
  
  
# t = int(inut())
# for _ in range(t):
# 	s1=list(map(int,input().split()))  
# 	a = []
# 	index = []
# 	for i in range(len(s1)-1):

# 		a.append(s1[i]-s1[i+1])
# 		index.append(i)

# 	zipped = list(zip(a,index))
# 	result = sorted(zipped, key = lambda x: x[1]) 	




# t = int(input())
# for _ in range(t):
# 	# t1 = int(input())
# 	s1=list(map(int,input().split()))  
# 	x = s1[0]
# 	n = s1[1]
# 	m = s1[2]
# 	ans = 0
# 	if(x<=0):
# 		ans = 1
# 	else:
# 		while(x>=20 and n>0):
# 			x = x//2+10
# 			# print(x)
# 			n-=1
# 			if(x<=0):
# 				ans = 1
# 				# print('YES')
				
# 		while(m>0):
# 			x= x-10
# 			m = m-1
# 			# print(x)
# 			if(x<=0):
# 				ans = 1
# 				# print('YES')
# 				# return
	
# 	if ans==1:
# 		print('YES')
# 	else:
# 		print("NO")				



	
		


	# print(d)			



# def detectLoop(head):
#     #code here
	
#     slow = head
#     fast = head
#     ans = 0
#     while slow != None and fast != None and ans = 0 :
#         slow = slow.next
#         fast = fast.next.next
		
#         if(slow == fast):
#             ans = 1
		
	
#     return ans        









#code

# t = int(input())
# for _ in range(t):
# 	# t1 = int(input())
# 	t1 = int(input())
# 	s1=list(map(int,input().split()))   
# 	stack = []
# 	ans=[]
# 	for i in range(t1-1,-1,-1):
# 		if(len(stack)==0):
# 			ans.insert(0,-1)
# 			stack.append(s1[i])
# 		else:
# 			while(len(stack)>0):
# 				if(s1[i]>stack[-1]):
# 					stack.pop(-1)
# 				else:
# 					break
# 			if(len(stack)==0):
# 				ans.insert(0,-1)
# 				stack.append(s1[i])
# 			else:     
# 				ans.insert(0,stack[-1])
# 				stack.append(s1[i])
	  
# 	print(ans)           
				
		
		
# 	




# t=list(map(int,input().split()))		
# s=list(map(int,input().split()))		
 
# temp = 0
# for i in s:
#   temp += i

# # print(temp)
# if(t[0]-temp>=0):
#   print([0]-temp)
# else:
#   print(-1)



# t = int(input())

# for i in range(t):
# 	n = int(input())
# 	# print(s)
# 	s=list(map(int,input().split()))		


# 	ans = []
	

# 	i = 0
# 	while i < len(s):
# 		if s[i] < 0:
# 			max1 = s[i]
# 			# print(s[i])
# 			# print(i)
# 			while s[i] < 0 and i < n:
# 				# print(i)

# 				if(s[i]>max1):
# 					max1 = s[i]
				
# 				i += 1
# 				if i == n:
# 					break
# 			ans.append(max1)
			
# 		else:
# 			max1 = s[i]
# 			while s[i] > 0  and i < n:
# 				if(s[i]>max1):
# 					max1 = s[i]
# 				i += 1
# 				if i == n:
# 					break
# 			ans.append(max1)
			

# 	print(sum(ans))



	
# t = int(input())

# for i in range(t):
# 	n=list(map(int,input().split()))		
	
# 	s=list(map(int,input().split()))		


# 	doc = {}
# 	ans = 0

# 	for i in range(n[0]//2):
# 		k = s[i]+s[n[0]-i-1]
# 		if(k not in doc):
# 			doc[k] = 1
# 		else:
# 			doc[k] +=1


# 	# print(doc)			
# 	ka=[]
# 	k = max(doc.items())
# 	k = k[1]
# 	for i in doc:
# 		if doc[i] == k:
# 			ka.append(i)
# 	# print(k)
# 	# print(ka)
# 	# if(len(ka)>1):
# 	# 	k = n[1]+1
# 	# else:
# 	k = sum(ka)//len(ka)	
# 	# k = min(i for i in ka if i >= n[1])
# 	for i in range(n[0]//2):
# 		t1 = s[i]
# 		t2 = s[n[0]-i-1]
# 		# print(t1,t2)
# 		if(t1+t2==k):
# 			ans = ans
# 		else:
# 			if(t1+t2<k):
# 				if(max(t1,t2)+n[1]>=k):
# 					ans += 1
# 				else:
# 					ans+=2	
# 			else:
# 				if(min(t1,t2)+0<=k):
# 					ans+=1
# 				else:
# 					ans+=2

# 	print(ans)							

# 			



# t = int(input())

# for _ in range(t):
# 	n = int(input())
# 	s = list(map(int,input().split()))

# 	fmin = 1
# 	fminindex = n
# 	falg = True

# 	while(i<=n):
# 		if(s[i-1] == fmin):
# 			temp = s[i-1]
# 			t2 = 0
# 			while(i<=fminindex):
# 				if(s[i-1]!=temp+t2):
# 					falg = False
# 				t2 += 1
# 				i = i+1
					
	



t = int(input())

for _ in range(t):
	n = input()
	# print(len(n))
	one = 0
	zero = 0
	ans=''
	for i in n:
		# print(i)
		if (i =='1'):	
			one+=1
		else:
			zero+=1

	if(min(one,zero) == 0):
		print(n)
	else:
		if(n[0]=='1'):
			ans = '10'*len(n)
		else:
			ans = '01'*len(n)
		print(ans)