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 JAVA):

Solution:
	import java.util.*;


import java.io.*;
	import java.math.*;
	import java.awt.geom.*;
	 
	import static java.lang.Math.*;
	 
	 public class Solution implements Runnable {
		
		 int mod1=(int)1e9+7;
		 int mod2=998244353;
	     
		 public void solve() throws Exception {
			 int t=sc.nextInt();
			 while(t-->0)
			 {
				 String s=sc.nextToken();
				 int len=s.length();
				 int count1=0;
				 int count0=0;
				 for(int i=0;i<len;i++)
				 {
					 if(s.charAt(i)=='1') count1++;
					 else count0++;
				 }
				 if( count1 == len || count0 == len )
				 {
					 for(int i=0;i<len;i++)
					 {
						 out.print(count1==len?"1":"0");
					 }
				 }
				 else
				 {
					 for(int i=0;i<len;i++)
					 {
						 out.print(s.charAt(0)=='1'?"10":"01");
					 }
				 }
				 out.println();
				
			 }
				
				
				
		 }
				
		 
	    
	    static long power(long x, long y, long p) 
	    { 
	       
	        long res = 1;      
	       
	        x = x % p;  
	  
	       if (x == 0) return 0;    
	  
	        while (y > 0) 
	        { 
	            if((y & 1)==1) 
	                res = (res * x) % p; 
	            y = y >> 1;  
	            x = (x * x) % p;  
	        } 
	        return res; 
	    } 
	    
	    		
	    
	    
	    
	    
	    
	    static Throwable uncaught;
	 
	    BufferedReader in;
	    FastScanner sc;
	    PrintWriter out;
	 
	    @Override
	    public void run() {
	        try {
	            in = new BufferedReader(new InputStreamReader(System.in));
	            out = new PrintWriter(System.out);
	            sc = new FastScanner(in);
	            solve();
	        } catch (Throwable uncaught) {
	            Solution.uncaught = uncaught;
	        } finally {
	            out.close();
	        }
	    }
	 
	    public static void main(String[] args) throws Throwable {
	        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
	        thread.start();
	        thread.join();
	        if (Solution.uncaught != null) {
	            throw Solution.uncaught;
	        }
	    }
	 
	}
	 
	class FastScanner {
	 
	    BufferedReader in;
	    StringTokenizer st;
	 
	    public FastScanner(BufferedReader in) {
	        this.in = in;
	    }
	 
	    public String nextToken() throws Exception {
	        while (st == null || !st.hasMoreTokens()) {
	            st = new StringTokenizer(in.readLine());
	        }
	        return st.nextToken();
	    }
	 
	    public int nextInt() throws Exception {
	        return Integer.parseInt(nextToken());
	    }
	    
	    public int[] readArray(int n) throws Exception {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
	 
	    public long nextLong() throws Exception {
	        return Long.parseLong(nextToken());
	    }
	 
	    public double nextDouble() throws Exception {
	        return Double.parseDouble(nextToken());
	    }
	 
	}