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:
from math import factorial as fac
from collections import defaultdict
from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
sys.setrecursionlimit(10**6)


def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())

NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
from collections import deque, defaultdict 
import heapq

def bfs(V, E):
	s = set()
	print('\n'.join(map(str,E.items())))
	cnt = 0 
	for v in V:
		if v in s:
			continue
		q = deque([])
		s.add(v)
		q.append(v)
		while len(q) > 0:
			x = q.popleft()
			for e in E[x]:
				if e not in s:
					s.add(e)
					q.append(e)
			print(q)
		cnt += 1
	return cnt
		
from typing import List, Tuple

def regular_bs(L,x,l=None,r=None):
	l = 0 if l == None else l
	r = len(L) if r == None else r
	while (r-l) > 1:
		m = (r+l)//2
		l = m if L[m] <= x else l
		r = m if L[m] > x else r
	cnt = 0
	return l

def binary_count_smaller(L, x):
	l = 0
	if x < L[0]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] < x:
			l = mid
		else:
			r = mid
	return l + 1
def binary_count_larger(L, x):
	l = 0
	if x > L[-1]:
		return 0
	r = len(L)
	while r - l > 1:
		mid = (l+r)//2
		if L[mid] <= x:
			l = mid
		else:
			r = mid
	return len(L) - (r-1)

from itertools import product

def solution(A):
	if ('1' not in A) or ('0' not in A):
		return A
	res = []
	for i in range(0,len(A) - 1):
		if A[i] == '1' and A[i+1] == '1':
			res.append('1')
			res.append('0')
		elif A[i] == '0' and A[i+1] == '0':
			res.append('0')
			res.append('1')
		else:
			res.append(A[i])
	res.append(A[-1])
	return ''.join(res)

	

def main():
	T = read_int()
	for i in range(T):
		A = f.readline().strip()
		print(solution(A))


if __name__ == '__main__':
	main()
# print(regular_bs([1,2],1))