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:
import math
import sys,collections
from sys import stdin, stdout  
#MAXN = 10000001

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip() 
def input(): return sys.stdin.readline().strip()
#spf = [0 for i in range(MAXN)] 
def file():
	sys.stdin = open('input.py', 'r')
	sys.stdout = open('output.py', 'w') 
def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x    
def sieve(): 
	spf[1] = 1
	for i in range(2, MAXN): 
		spf[i] = i 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 
				if (spf[j] == j): 
					spf[j] = i 
def getFactorization(x): 
	ret = list() 
	while (x != 1): 
		ret.append(spf[x]) 
		x = x // spf[x] 

	return ret 
def getFloor(A, x):

    (left, right) = (0, len(A) - 1)

    ind,floor = -1,-1
    while left <= right:
        mid = (left + right) // 2
        '''if A[mid] == x:
            return mid'''
        if x < A[mid]:
            right = mid - 1
        else:
            floor = A[mid]
            ind=mid
            left = mid + 1
            
    return ind
def check(st) : 
  
    # Compute sum of digits 
    n = len(st) 
    digitSum = 0
      
    for i in range(0,n) : 
        digitSum = digitSum + (int)(st[i]) 
  
    # Check if sum of digits 
    # is divisible by 9. 
    return (digitSum % 9 == 0)     
def isPowerOfTwo(n): 
    if (n == 0): 
        return False
    while (n != 1): 
            if (n % 2 != 0): 
                return False
            n = n // 2
            
              
    return True
def kitte(n):
	c=0
	while(n!=0):
		n=n//2
		c+=1
	return c	
def aa(b,c):
	m=min(b,c)
	b-=m
	c-=m
	if(c>0 and b>0):
		return(m+((b+c)//3))
	else:
		return(m)
def bb(a,c):
	m=min(a,c)
	a-=m
	c-=m
	if(c>0 and a>0):
		return(m+((a+c)//3))
	else:
		return(m)
def cc(b,a):
	m=min(b,a)
	b-=m
	a-=m
	if(a>0 and b>0):
		return(m+((b+a)//3))
	else:
		return(m)		
#file()
#sieve() 
mod=(10**9)+7	
def main():
	for tt in range(int(input())):
		s=list(input())
		n=len(s)
		if(len(set(s))==1):
			print("".join(s))
		else:
			print('10'*(n))


	



	

	
			


		




		






		







			



	

	




	





















	




















		
			


		

			

		





			

	























				

	















	

	










if __name__ == '__main__':
    main()