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.io.*;

import java.util.*;



public class hello2
 {static class FastReader 
	
       { 
	 int l;
           BufferedReader br; 
           StringTokenizer st; 
     
           public FastReader() 
           { 
               br = new BufferedReader(new
                        InputStreamReader(System.in)); 
           } 
     
           String next() 
           { 
               while (st == null || !st.hasMoreElements()) 
               { 
                   try
                   { 
                       st = new StringTokenizer(br.readLine()); 
                   } 
                   catch (IOException  e) 
                   { 
                       e.printStackTrace(); 
                   } 
               } 
               return st.nextToken(); 
           } 
     
           int nextInt() 
           { 
               return Integer.parseInt(next()); 
           } 
     
           long nextLong() 
           { 
               return Long.parseLong(next()); 
           } 
     
           double nextDouble() 
           { 
               return Double.parseDouble(next()); 
           } 
     
           String nextLine() 
           { 
               String str = ""; 
               try
               { 
                   str = br.readLine(); 
               } 
               catch (IOException e) 
               { 
                   e.printStackTrace(); 
               } 
               return str; 
           } 
         
       }
    
    static String sum (String s)
    {
        String s1 = ""; 
        
        if(s.contains("a"))
            s1+="a";
        if(s.contains("e"))
            s1+="e";
        if(s.contains("i"))
            s1+="i";
        if(s.contains("o"))
            s1+="o";
        if(s.contains("u"))
            s1+="u";
        
            return s1;
            
        
    }
    

    public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm) 
    { 
        // Create a list from elements of HashMap 
        List<Map.Entry<String, Integer> > list = 
               new LinkedList<Map.Entry<String, Integer> >(hm.entrySet()); 
  
        // Sort the list 
        Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() { 
            public int compare(Map.Entry<String, Integer> o1,  
                               Map.Entry<String, Integer> o2) 
            { 
                return (o1.getValue()).compareTo(o2.getValue()); 
            } 
        }); 
          
        // put data from sorted list to hashmap  
        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>(); 
        for (Map.Entry<String, Integer> aa : list) { 
            temp.put(aa.getKey(), aa.getValue()); 
        } 
        return temp; 
    } 
    
    
public static void main(String args[])
    {
        FastReader input =new FastReader();
      
       
        int t = input.nextInt();
        
        
        while(t-->0)
        {
        	
        	 
        	 String s = input.next();
        	 
        	 int n = s.length();
        	 StringBuilder ans = new StringBuilder();
        	 int flag=0;
        	 if(n>=3)
        	 {
        		 for(int i=0;i<n-1;i++)
        		 {
        			 if(s.charAt(i)==s.charAt(i+1))
        			 {
        				 
        			 }
        			 else
        			 {
        				 flag=1;
        				 break;
        			 }
        		 }
        		 
        		 if(flag==0)
        			 System.out.println(s);
        		 else
        		 {
        			 if(s.charAt(0)=='0')
        			 {
        				 for(int i=0;i<2*n;i++)
        				 {
        					 if(i%2==0)
        					 ans.append("0");
        					 else
        						 ans.append("1");
            					 
        				 }
        				 System.out.println(ans);
        			 }
        			 else
        			 {
        				 for(int i=0;i<2*n;i++)
        				 {
        					 if(i%2==1)
        					 ans.append("0");
        					 else
        						 ans.append("1");
            					 
        				 }
        				 System.out.println(ans);
        			 }
        				 
        		 }
        	 }
        	 else
        		 System.out.println(s);
        	 
             
        }
        	
        	
        	
        	
        	
        	
        	
        	
        
        }



    
    

public static boolean range(int x,int y,int n,int m)
{
	if(x<0 || x>n-1 || y<0 || y>m-1)
		return false;
	
	
	return true;
}
   
public static int even_element(int b[],int n)
{
	int c[] = new int[n/2 + 1];
	int l=0;
	for(int i=1;i<n;i+=2)
	{
		c[l] = b[i];
		
		System.out.print(c[l] + " ");
		l++;
	}
	System.out.println();
	if(c.length!=1)
	{
		return even_element(c,n/2);
	}
	else
		return c[0];
}

      
       	
        	
        	
 
    
    static boolean isPrime(int n) 
    { 
        
        if (n <= 1) 
            return false; 
  
        
        for (int i = 2; i < n; i++) 
            if (n % i == 0) 
                return false; 
  
        return true; 
    } 
 }
 
 
class Pair
{
    int x,y;
    Pair(int x,int y)
    {
        this.x=x;
        this.y=y;
    }
}