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.sql.SQLOutput;
import java.sql.SQLOutput;
import java.util.*;



public class Solution {

    public static void main(String[] args) throws IOException
    {
       
    	
        
        
    	int t = sc.nextInt();
    	
    	while(t-->0)
    	{
    		String st = sc.nextLine();
    		
    		int zc=0,oc=0;
    		
    		int n = st.length();
    		
    		for(int i=0;i<n;i++)
    		{
    			char ch = st.charAt(i);
    			if(ch=='1')oc++;
    			else zc++;
    			
    		}
    		
    		if(zc==0||oc==0)
    		{
    			System.out.println(st);
    		}
    		else
    		{
    			int rt = Math.max(zc,oc);
    			StringBuilder sb = new StringBuilder();
    			
    			for(int i=0;i<n;i++)sb.append("10");
    			
    			String sa = sb.toString();
    			System.out.println(sa);
    		}
    	}
        


    }









    static  class MyScanner
    {

        BufferedReader br;
        StringTokenizer st;

        public MyScanner()
        {
            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 MyScanner sc = new  MyScanner();
    static PrintWriter pw = new PrintWriter(System.out, true);

    static class Comp implements Comparator<Point>
    {

        @Override
        public int compare(Point arg0, Point arg1) {

            if(arg0.x>arg1.x)return 1;
            if(arg0.x<arg1.x)return -1;
            return 0;
        }

    }



    static class Point
    {
        int x,y,ind;

        public Point(int a, int b)
        {
            x=a;
            y=b;
            ind=0;
        }

        @Override
        public boolean equals(Object o)
        {

            // If the object is compared with itself then return true
            if (o == this) {
                return true;
            }
    			 
    			        /* Check if o is an instance of Complex or not
    			          "null instanceof [type]" also returns false */
            if (!(o instanceof Point)) {
                return false;
            }

            // typecast o to Complex so that we can compare data members
            Point c = (Point) o;

            // Compare the data members and return accordingly
            return x==c.x&&y==c.y;

        }

    }






}