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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Nikita Mikhailov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BDvoichniiPeriod solver = new BDvoichniiPeriod();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class BDvoichniiPeriod {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            String str = in.readToken();

            int cnt0 = 0, cnt1 = 0;
            for (int i = 0; i < str.length(); i++) {
                cnt0 += str.charAt(i) == '0' ? 1 : 0;
                cnt1 += str.charAt(i) == '1' ? 1 : 0;
            }

            if (cnt0 == 0 || cnt1 == 0 || (cnt0 + cnt1 == 1)) {
                out.println(str);
                return;
            }

            StringBuilder sb = new StringBuilder();


            int ind = 2;
            char first = str.charAt(0);
            char second = str.charAt(1);

            sb.append(first);

            if (second == first) {
                ind--;
                second = first == '0' ? '1' : '0';
            }
            sb.append(second);


            while (ind < str.length()) {
                char cur = str.charAt(ind);

                if (cur == first) {
                    ind++;
                }
                sb.append(first);

                char next = ind >= str.length() ? 0 : str.charAt(ind);
                if (next == second) {
                    ind++;
                }
                sb.append(second);
            }
            out.println(sb.toString());
        }

    }

    static class FastScanner {
        private StringTokenizer st;
        private BufferedReader in;

        public FastScanner(final InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public String readToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public String next() {
            return readToken();
        }

    }
}