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.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}


    long get(int p, int b){
        long s = 0;
        long f = 1;
        while(p!=0){
            s += f*(p%10);
            if(p%10>=b){
                return -10000;
            }
            p /= 10;
            f *= b;
        }
        return s;
    }


    long get(int num){
        if(num==1){
            return 0;
        }
        long s = 1;
        for(int i=2;i*i<=num;++i){
            if(num%i==0){
                s += i;
                if(num/i!=i){
                    s += num/i;
                }
            }
        }

        return s;
    }


    long inv(long a, long MOD) {
        //return fpow(a, MOD-2, MOD);
        return a==1?1:(long )(MOD-MOD/a)*inv(MOD%a, MOD)%MOD;
    }

    // 计算某个特别大的组合数
    long C(long n,long m, long MOD) {
        if(m+m>n)m=n-m;
        long up=1,down=1;
        for(long i=0;i<m;i++)
        {
            up=up*(n-i);
            down=down*(i+1);
        }
        return up/down;
    }

    boolean ok(String s){
        for(int i=0;i<s.length()/2;++i){
            if(s.charAt(i)!=s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }

    int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
    int[] revContor(int bits, int rank) {
        rank--; //有 rank - 1 个排列比目标序列要小
        boolean vis[] = new boolean[bits+1];
        int res[] = new int[bits];

        int n, residue = rank;
        for (int i = 0; i < bits; ++i) {
            n = residue / (fact[bits - i - 1]);
            residue = residue % (fact[bits - i - 1]);

            for (int j = 1; j <= bits; ++j) {
                if (!vis[j] && n--==0) {
                    vis[j] = true;
                    res[i] = j-1;
                    break;
                }
            }
        }
        return res;
    }

    static long mul(long a, long b, long p)
    {
        long res=0,base=a;
        while(b>0)
        {
            if((b&1L)>0)
                res=(res+base)%p;
            base=(base+base)%p;
            b>>=1;
        }
        return res;
    }

    static long mod_pow(long k,long n,long p){
        long res = 1L;
        long temp = k%p;
        while(n!=0L){
            if((n&1L)==1L){
                res = mul(res,temp,p);
            }
            temp = mul(temp,temp,p);
            n = n>>1L;
        }
        return res%p;
    }

    boolean ok(int i){
        if(i==2||i==3||i==5||i==7){
            return false;
        }
        int v = 1;int ct = 0;
        while(v<i){
            v *= 10;
            ct++;
        }

        while(v!=1){
            int cur = i%v;
            if(visit[cur]) return false;
            v/=10;
        }
        while(i!=0){
            int cur = i;
            if(visit[i]) return false;
            i/=10;
        }

        return true;
    }


    boolean visit[];
    void solve() {

//        Set<Integer> st=  new HashSet<>();
//
//        int s = 0;
//        for(int i=1;i<=1000;i++){
//            s = i*(i+1)/2;
//            st.add(s);
//        }
//        Set<Integer> st1 =  new HashSet<>();
//        for(int i=1;i<=1000;i++){
//            s = i*(2*i-1)/2;
//            if(st.contains(s)){
//                st1.add(s);
//            }
//        }
//        Set<Integer> st2 =  new HashSet<>();
//        for(int i=1;i<=10000;i++){
//            s = i*(3*i-1)/2;
//            if(st1.contains(s)){
//                st2.add(s);
//            }
//        }
//        int me =1;

        int t  =ni();
        for(int j=0;j<t;++j){
           String s = ns();
           int one = 0;
           for(char c:s.toCharArray()){
               one += c-'0';
           }
           if(one==0||one==s.length()){
               println(s);continue;
           }


           StringBuilder sb = new StringBuilder();
           for(int i=0;i<s.length()-1;++i){
               String ck = s.substring(i,i+2);
               if(ck.equals("00")){
                   sb.append("01");
               }else if(ck.equals("11")){
                   sb.append("10");
               }else if(ck.equals("10")){
                   sb.append("1");
               }else{
                   sb.append("0");
               }
           }
           sb.append(s.charAt(s.length()-1));
           println(sb);


        }








    }

    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    int gcd(int a,int b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
        //   is  = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P3119_6.in");
        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
    void printf(String f,Object ... args){out.printf(f, args);}
}