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

/**
 * Created by Katushka on 11.03.2020.
 */
public class B {
    static int[] readArray(int size, InputReader in) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt();
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int t = in.nextInt();
        for (int ii = 0; ii < t; ii++) {
            String s = in.nextString();
            char ch = s.charAt(0);
            int i = 1;
            while (i < s.length() && s.charAt(i) == ch) {
                i++;
            }
            if (i == s.length()) {
                out.println(s);
            } else {
                StringBuilder ans = new StringBuilder();
                int j = 0;
                i = 0;
                char ch1 = (ch == '0' ? '1' : '0');
                while (i < s.length()) {
                    char nextCh;
                    if (j % 2 == 0) {
                        nextCh = ch;
                    } else {
                        nextCh = ch1;
                    }
                    if (nextCh == s.charAt(i)) {
                        i++;
                    }
                    ans.append(nextCh);
                    j++;
                }
                out.println(ans.toString());
            }
        }

        out.close();
    }

    private static void solve(int[] hasParent, Map<Integer, List<Integer>> edges, int[] exist, int n) throws CycleFoundException {
        int[] visitedMins = new int[n + 1];
        int[] inProcess = new int[n + 1];

        for (int i = 1; i < hasParent.length; i++) {
            if (hasParent[i] == 0) {
                if (visitedMins[i] == 0) {
                    dfs(edges, visitedMins, i, inProcess, Integer.MAX_VALUE, exist);
                }
            }
        }

        for (int i = 1; i < visitedMins.length; i++) {
            if (visitedMins[i] == 0) {
                throw new CycleFoundException();
            }
        }
    }

    private static class CycleFoundException extends Exception {
    }

    private static int dfs(Map<Integer, List<Integer>> edges, int[] visited, Integer v, int[] inProcess, int min, int[] existQuantors) throws CycleFoundException {
        inProcess[v] = 1;
        if (v > min) {
            existQuantors[v] = 1;
        }
        int result = v;
        if (edges.containsKey(v)) {
            for (Integer u : edges.get(v)) {
                if (inProcess[u] == 1) {
                    throw new CycleFoundException();
                }
                int childMin;
                if (visited[u] == 0) {
                    childMin = dfs(edges, visited, u, inProcess, Math.min(min, v), existQuantors);
                } else {
                    childMin = visited[u];
                }
                if (childMin < v) {
                    existQuantors[v] = 1;
                }
                result = Math.min(result, childMin);
            }
        }
        visited[v] = result;
        inProcess[v] = 0;
        return result;
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }
    }
}