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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
using namespace std;
const long double eps = 1e-9;
const long double PI = acos(-1);
const long long inf = 1e18 + 1329;
const long double E = 2.71828182845904523536028747135266249775724709369995;
vector<long long> mods = {1000065757, 1000570057, 1004571329,
                          1000580179, 1000057769, 1000001329,
                          1000006957, 1000056157, 1001001329};
vector<long long> hashpows = {29, 31, 37, 43, 47, 53, 59, 157, 179, 257};
mt19937 rnd((unsigned int)chrono::high_resolution_clock::now()
                .time_since_epoch()
                .count() +
            (unsigned int)1329);
long long hashmod = mods[rnd() % mods.size()];
long long hashpow = hashpows[rnd() % hashpows.size()];
template <class T>
istream& operator>>(istream& stream, vector<T>& v) {
  for (int i = 0; i < v.size(); ++i) {
    cin >> v[i];
  }
  return stream;
}
template <class T>
ostream& operator<<(ostream& stream, vector<T>& v) {
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << '\n';
  return stream;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  srand((unsigned int)time(NULL));
  int t;
  cin >> t;
  while (t--) {
    string t;
    cin >> t;
    bool has0 = false, has1 = false;
    int n = (int)t.size();
    for (int i = 0; i < n; ++i) {
      has0 |= (t[i] == '0');
      has1 |= (t[i] == '1');
    }
    if (has0 + has1 == 1) {
      cout << t << '\n';
    } else {
      for (int i = 0; i < 2 * n; ++i) {
        cout << i % 2;
      }
      cout << '\n';
    }
  }
}