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.
#alpha = [ chr(i) for i in range(ord('a'),ord('z')+1)]
arr  = [[],[]]
def out1(x,n,m):
    # print(n,m)
    # if arr[n][m] != True:
    #     return False
    if x <= 0:

        return True
    if n <= 0 :
        if (x-10*m) > 0 :
            # arr[n][m] = False
            return False
        else:
            return True
    if m<=0 :
        # arr[n][m] = False
        return False
    # if n < 1:
    #     return out1(x-10,n,m-1)
    # elif m <= 0:

        
    return out1(x//2+10,n-1,m) or out1(x-10,n,m-1)



def out():
    s = input()
    if len(s) <3:
        print(s)
        return
    flag = 0
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            flag =1 
            break
    if flag == 0:
        print(s)
        return

    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print(s[i],end='')
            if s[i] == '1':
                print('0',end='')
            else:
                print('1',end='')
            # print(s[i+1],end='')
        else:
            print(s[i],end='')
    print(s[len(s)-1])
    return



ans = 0 
for i in range(int(input())):
    out()