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.*;
import java.math.*;

public class B {
    static final boolean RUN_TIMING = false;
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1024);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1024);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int zzz = ipar();
        for (int zz = 0; zz < zzz; zz++) {
            char[] arr = spar().toCharArray();
            int n = arr.length;
            boolean same = true;
            for (int i = 0; i < n-1; i++) {
                if (arr[i] != arr[i+1]) {
                    same = false;
                    break;
                }
            }
            if (same) {
                out.println(arr);
                continue;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n-1; i++) {
                sb.append(arr[i]);
                if (arr[i] == arr[i+1]) {
                    sb.append(arr[i] == '1' ? '0' : '1');
                }
            }
            sb.append(arr[n-1]);
            out.println(sb);
        }
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        StringBuilder sb = new StringBuilder(1024);
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            sb.append((char)c);
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return sb.toString();
    }

    public String linepar() throws IOException {
        StringBuilder sb = new StringBuilder(1024);
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            sb.append((char)c);
        }
        return sb.toString();
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new B().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time/1000000.0);
        }
        out.flush();
        in.close();
    }
}