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:
'''test=int(input())
for i in range(test):
    n=int(input())
    a=[int(j) for j in input().split()]
    b=[int(k) for k in input().split()]
    ans=""
    if a[0]!=b[0]:
        ans="NO"
    else:
        pos=0
        neg=0
        for i in range(n):
            if a[i]>b[i] and  not neg:
                ans="NO"
                break

            elif a[i]<b[i] and not pos:
                ans="NO"
                break
            else:
                if a[i]==1:
                    pos+=1
                elif a[i]==-1:
                    neg+=1
                ans="YES"
    print(ans)'''

'''n=int(input())
nums=[int(i) for i in input().split()]
from collections import defaultdict
hashmap=defaultdict(int)
sum_=0
ans=0
for i in range(n):
    sum_+=nums[i]
    if sum_ in hashmap:
        ans+=(n-i)*hashmap[sum_]
        hashmap[sum_]+=1
    elif sum_ not in hashmap and not sum_:
        ans+=n-i
        hashmap[0]+=1
    else:
        hashmap[sum_]+=1
print(int(n*(n+1)/2-ans))'''

'''import heapq
test=int(input())
for i in range(test):
    n=int(input())
    monst=[]
    kill=[0]*n
    for j in range(n):
        a,b=[int(i) for i in input().split()]
        monst.append((a,b,j))
    heap=sorted(monst,key=lambda x:x[0]-x[1])
    penalty=[0]*n
    bull=0
    for k in range(n):
        if not kill[heap[k][2]]:
            bull+=heap[k][0]
            start=k
            next_=0 if k==n-1 else k+1
            while monst[]

'''
'''test=int(input())
for i in range(test):
    a,b,c,d=[int(i) for i in input().split()]
    first=b
    second=c
    third=c
    
    print(first,second,third,sep=" ")'''

'''
test=int(input())
for i in range(test):
    x,n,m=[int(i) for i in input().split()]
    ans="NO"
    if n==m==0:
        ans="NO"
    else:
        spell1=0
        spell2=0
        for i in range(n):
            if x<=0 or x<=m*10:
                ans="YES"

            x=int(x/2)+10

        if x<=0 or x<=m*10:
            ans="YES"



    print(ans)
    '''

'''n,k=[int(i) for i in input().split()]
from collections import defaultdict
graph=defaultdict(list)
for i in range(n-1):
    p,c=[int(i) for i in input().split()]
    graph[p].append(c)
    graph[c].append(p)

size=[0]*(n+1)
depth=[0]*(n+1)
depth[0]=-1
ans=[0]*(n+1)
def dfs(p,c):
    size[c]=1
    depth[c]=1+depth[p]
    for j in graph[c]:
       if j!=p:
            size[c]+=dfs(c,j)
    ans[c]=size[c]-depth[c]
    return size[c]    
            
    

dfs(0,1)

ans.sort(reverse=True)
res=sum([ans[a] for a in range(n-k)])
print(res)

print(ans)
'''
'''test=int(input())
def check(arr,min_,max_,k):
    if len(arr)<2:
        return [min_,max_]
    min_=max(min(arr[0],arr[-1])+1,min_)
    max_=min(max(arr[0],arr[-1])+k,max_)
    return check(arr[1:-1],min_,max_,k) 

def again(arr,left,right,dict_):
    if len(arr)<2:
        return 
    k=arr[0]+arr[-1]
    if k>=left and k<=right:
        dict_[k]+=1
    again(arr[1:-1],left,right,dict_)

from collections import defaultdict
for i in range(test):
    n,k=[int(t) for t in input().split()]
    arr=[int(k) for k in input().split()]
    min_,max_=check(arr,0,float("inf"),k)
    option=defaultdict(int)
    again(arr,min_,max_,option)
    #print(max_)
    if not len(option.values()):
        print(int(n/2))
    else:
        print(int(n/2-max(option.values())))'''


'''test=int(input())
from collections import defaultdict
for i in range(test):
    n=int(input())
    nums=[int(i) for i in input().split()]
    cnt=defaultdict(list)
    i=0
    flag=0
    cnt[0].append(nums[0])
    for k in range(1,n):
        if nums[k]>0 and nums[k-1]<0 or (nums[k]<0 and nums[k-1]>0):
            flag=1
        if flag:
            i+=1
            cnt[i].append(nums[k])
            flag=0
        else:
            cnt[i].append(nums[k])
    ans=0
    for t in cnt.values():
        ans+=max(t)
    print(ans)'''

'''test=int(input())
for i in range(test):
    x,y=[int(i) for i in input().split()]
    a,b=[int(i) for i in input().split()]
    ans=0
    if x==0 and y==0:
        ans=0
    elif x>=0 and y>=0:
        min_=min(x,y)
        max_=max(x,y)
        if x!=y:
            ans=min((max_-min_)*a+min_*b,(x+y)*a)
        else:
            ans=min(y*b,2*a*y)
    print(ans)
'''
test=int(input())
for i in range(test):
    t=input()
    ans=""
    if len(t)<=2:
        ans=t
    else:
        if "0" not in t or "1" not in t:
            ans=t
        else:
            for i in range(len(t)-1):
                if t[i]==t[i+1]:
                    ans+=t[i]+( "0"if t[i]=="1"else "1")
                else:
                    ans+=t[i]
        ans+=t[len(t)-1]    




    print(ans)