#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
#pragma warning(disable : 4996)
#pragma hdrstop
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T>
constexpr auto has_begin(int) -> decltype(std::begin(std::declval<T>()), true) {
  return true;
}
template <typename T>
constexpr bool has_begin(...) {
  return false;
}
template <typename T>
using is_container = std::integral_constant<bool, has_begin<T>(0)>;
template <typename T, typename... Types>
using is_one_of = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using is_sane_integer = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !is_one_of<typename std::remove_cv<T>::type, char, signed char,
                   unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
std::string to_string(const std::string& s) { return '"' + s + '"'; }
std::string to_string(const char* s) { return to_string(std::string(s)); }
std::string to_string(const char ch) { return {'\'', ch, '\''}; }
std::string to_string(const bool b) { return (b ? "true" : "false"); }
template <typename T,
          typename std::enable_if<Disjunction<
              is_sane_integer<T>::value,
              std::is_floating_point<T>::value>::value>::type* = nullptr>
std::string to_string(const T value) {
  return std::to_string(value);
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>&);
template <typename T,
          typename std::enable_if<is_container<T>::value>::type* = nullptr>
std::string to_string(const T& container) {
  bool is_first = true;
  std::string res = "{";
  for (const auto& x : container) {
    if (!is_first) {
      res += ", ";
    }
    is_first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>& p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
std::vector<std::string> vec_splitter(std::string s) {
  s += ',';
  std::vector<std::string> res;
  while (!s.empty()) {
    const size_t pos = s.find(',');
    res.emplace_back(s.substr(0, pos));
    s = s.substr(pos + 1);
  }
  return res;
}
void debug_out(std::vector<std::string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  std::cerr << std::endl;
}
template <typename Head, typename... Tail>
void debug_out(std::vector<std::string> args, int idx, int LINE_NUM, Head H,
               Tail... T) {
  std::stringstream ss;
  ss << to_string(H);
  if (idx > 0) {
    std::cerr << ", ";
  } else {
    std::cerr << "Line(" << LINE_NUM << ") ";
  }
  std::cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
namespace std {
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
  for (auto& it : vec) {
    in >> it;
  }
  return in;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& rhs) {
  in >> rhs.first >> rhs.second;
  return in;
}
}  // namespace std
void assign_files_input_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  using value_type = T;
  constexpr explicit IntegerIterator(const value_type value) : value_(value) {}
  IntegerIterator& operator++() {
    ++value_;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value_;
    return copy;
  }
  IntegerIterator& operator--() {
    --value_;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value_;
    return copy;
  }
  constexpr value_type operator*() const { return value_; }
  constexpr bool operator==(const IntegerIterator rhs) const {
    return value_ == rhs.value_;
  }
  constexpr bool operator!=(const IntegerIterator rhs) const {
    return !(*this == rhs);
  }
  constexpr value_type operator+(const IntegerIterator rhs) const {
    return value_ + rhs.value_;
  }
  IntegerIterator& operator+=(const IntegerIterator rhs) const {
    value_ += rhs.value_;
    return *this;
  }
  constexpr value_type operator-(const IntegerIterator rhs) const {
    return value_ - rhs.value_;
  }
  IntegerIterator& operator-=(const IntegerIterator rhs) const {
    value_ -= rhs.value_;
    return *this;
  }

 private:
  value_type value_;
};
template <typename T>
class IntegerRange {
 public:
  using const_iterator = IntegerIterator<T>;
  constexpr IntegerRange(const T begin, const T end)
      : begin_(begin), end_(end) {}
  constexpr const_iterator begin() const { return const_iterator(begin_); }
  constexpr const_iterator end() const { return const_iterator(end_); }
  constexpr T size() const { return end_ - begin_; }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedRange {
 public:
  using const_iterator = typename std::decay<T>::type::const_iterator;
  using reverse_iterator = std::reverse_iterator<const_iterator>;
  explicit constexpr ReversedRange(const T& iterable)
      : begin_(iterable.begin()), end_(iterable.end()) {}
  constexpr reverse_iterator begin() const { return reverse_iterator(end_); }
  constexpr reverse_iterator end() const { return reverse_iterator(begin_); }

 private:
  const_iterator begin_;
  const_iterator end_;
};
template <typename T>
ReversedRange<T> reversed(T&& iterable) {
  return ReversedRange<T>{iterable};
}
template <typename T>
constexpr IntegerRange<T> range(const T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
constexpr IntegerRange<T> range(const T from, const T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T from, const T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from) {
  return reversed(range(from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from, const T to) {
  return reversed(range(to, from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from) {
  return reversed(range(from + 1));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from,
                                                            const T to) {
  return reversed(range(to, from + 1));
}
template <typename R>
void sort(R& range) {
  std::sort(range.begin(), range.end());
}
template <typename R, typename Comp>
void sort(R& range, Comp comp) {
  std::sort(range.begin(), range.end(), comp);
}
template <typename R>
void reverse(R& range) {
  std::reverse(range.begin(), range.end());
}
template <typename R, typename T>
auto lower_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto lower_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value, comp);
}
template <typename R, typename T>
auto upper_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto upper_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value, comp);
}
template <typename R>
auto min_element(const R& range) -> decltype(range.begin()) {
  return std::min_element(range.begin(), range.end());
}
template <typename R>
auto max_element(const R& range) -> decltype(range.begin()) {
  return std::max_element(range.begin(), range.end());
}
template <typename R>
bool next_permutation(R& range) {
  return std::next_permutation(range.begin(), range.end());
}
template <typename T>
void unique(std::vector<T>& range) {
  range.erase(std::unique(range.begin(), range.end()), range.end());
}
template <typename T>
void dedup(std::vector<T>& range) {
  sort(range);
  unique(range);
}
template <typename R>
R sorted(R range) {
  sort(range);
  return range;
}
template <typename R, typename Comp>
R sorted(R range, Comp comp) {
  sort(range, comp);
  return range;
}
static constexpr long double PI = 3.14159265358979323846;
static constexpr long double EPS = 1e-9;
static constexpr int32_t INF = 0x3f3f3f3f;
static constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr int32_t DX[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
static constexpr int32_t DY[8] = {0, 1, 0, -1, -1, 1, 1, -1};
static constexpr uint32_t kDayMonth[12] = {31, 28, 31, 30, 31, 30,
                                           31, 31, 30, 31, 30, 31};
enum Direction : uint8_t {
  Up,
  Right,
  Down,
  Left,
  UpLeft,
  UpRight,
  DownRight,
  DownLeft,
  North = Up,
  East = Right,
  South = Down,
  West = Left,
  NorthWest = UpLeft,
  NorthEast = UpRight,
  SouthEast = DownRight,
  SouthWest = DownLeft,
  Unknown = 255
};
namespace Random {
inline std::chrono::system_clock::rep current_timestamp() {
  return std::chrono::system_clock::now().time_since_epoch().count();
}
inline uint64_t get_new_rand_seed() {
  return static_cast<uint64_t>(current_timestamp());
}
inline uint64_t get_rand_seed() {
  static const uint64_t kRandSeed = get_new_rand_seed();
  return kRandSeed;
}
using Engine = std::mt19937_64;
template <typename T>
using Distribution = std::uniform_int_distribution<T>;
inline Engine& random_engine() {
  static Engine engine(get_rand_seed());
  return engine;
}
template <typename T>
inline T get(const T to) {
  Distribution<T> distribution(0, to);
  return distribution(random_engine());
}
template <typename T>
inline T get(const T from, const T to) {
  return get(to - from) + from;
}
template <typename T = int32_t>
inline T get() {
  return get(static_cast<T>(0), std::numeric_limits<T>::max());
}
}  // namespace Random
template <typename T,
          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
class SafeIntegralHash {
 public:
  const T kRandomValue = static_cast<T>(Random::current_timestamp());
  T operator()(const T& value) const { return value ^ kRandomValue; }
};
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMap = std::unordered_map<Key, Value, SafeIntegralHash<Key>>;
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiMap =
    std::unordered_multimap<Key, Value, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedSet = std::unordered_set<Key, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiSet =
    std::unordered_multiset<Key, SafeIntegralHash<Key>>;
namespace std {
template <typename T, typename U>
struct hash<std::pair<T, U>> {
  std::size_t operator()(const std::pair<T, U>& pair) const {
    return pair.first * 877117 + pair.second;
  }
};
}  // namespace std
template <typename T, typename std::enable_if<
                          std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return abs(a) < EPS;
}
template <typename T, typename std::enable_if<
                          !std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return a == 0;
}
template <typename T>
inline bool umin(T& a, const T& b) {
  return (b < a ? a = b, true : false);
}
template <typename T>
inline bool umax(T& a, const T& b) {
  return (a < b ? a = b, true : false);
}
template <typename T, size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
template <typename T>
inline bool is_leap_year(const T year) {
  return year % 400 == 0 || (year % 100 != 0 && (year & 3) == 0);
}
inline size_t get_days_in_month(const size_t month, const size_t year) {
  return kDayMonth[month] + (month == 1 && is_leap_year(year) ? 1 : 0);
}
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pli = std::pair<ll, int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vp = std::vector<pii>;
class HDvoichnayaMediana {
 public:
  static constexpr bool kWriteCaseNumber = false;
  static constexpr bool kMultiTest = true;
  ll go(ll left, ll right, ll pos, const std::vector<ll>& a) {
    if (left + 1 == right) {
      return left;
    }
    ll med = (left + right) / 2;
    auto count = [&a](const ll left, const ll right) {
      ll ans = right - left;
      for (ll x : a) {
        if (x >= left && x < right) {
          --ans;
        }
      }
      return ans;
    };
    ll cnt_l = count(left, med);
    ll cnt_r = count(med, right);
    if (pos > cnt_l) {
      return go(med, right, pos - cnt_l, a);
    } else {
      return go(left, med, pos, a);
    }
  }
  void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    std::vector<std::string> a(n);
    in >> a;
    std::vector<ll> vals;
    for (const auto& row : a) {
      ll val = 0;
      for (char ch : row) {
        val = val * 2 + (ch - '0');
      }
      vals.emplace_back(val);
    }
    ll total = (1LL << m);
    ll left = total - n;
    42;
    ll ans = go(0, total, (left - 1) / 2 + 1, vals);
    42;
    std::string binans = "";
    while (ans > 0) {
      binans += (ans % 2) + '0';
      ans /= 2;
    }
    reverse(binans);
    binans = std::string(m - binans.length(), '0') + binans;
    out << binans << std::endl;
  }
  HDvoichnayaMediana() {}
  static constexpr bool kUseCustomChecker = false;
  bool check(std::istringstream in, std::istringstream jury,
             std::istringstream out) {
    return true;
  }
  static constexpr size_t kGeneratedTestsCount = 0;
  static constexpr bool kStopAfterFirstFail = false;
  static void generate_test(std::ostream& test) {}
};
int main() {
  HDvoichnayaMediana solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  srand(time(nullptr));
  out << std::fixed << std::setprecision(16);
  if (HDvoichnayaMediana::kMultiTest) {
    size_t tests_count;
    in >> tests_count;
    for (size_t test_id : inclusiveRange<size_t>(1, tests_count)) {
      if (HDvoichnayaMediana::kWriteCaseNumber) {
        out << "Case #" << test_id << ": ";
      }
      solver.solve(in, out);
    }
  } else {
    solver.solve(in, out);
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Consider all binary strings of length m (1 ≤ m ≤ 60). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly 2^m such strings in total.

The string s is lexicographically smaller than the string t (both have the same length m) if in the first position i from the left in which they differ, we have s[i] < t[i]. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set n (1 ≤ n ≤ min(2^m-1, 100)) distinct binary strings a_1, a_2, …, a_n, each of length m. Thus, the set will have k=2^m-n strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from 0 to k-1. Print the string whose index is ⌊ (k-1)/(2) ⌋ (such an element is called median), where ⌊ x ⌋ is the rounding of the number down to the nearest integer.

For example, if n=3, m=3 and a=[010, 111, 001], then after removing the strings a_i and sorting, the result will take the form: [000, 011, 100, 101, 110]. Thus, the desired median is 100.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases. Then, t test cases follow.

The first line of each test case contains integers n (1 ≤ n ≤ min(2^m-1, 100)) and m (1 ≤ m ≤ 60), where n is the number of strings to remove, and m is the length of binary strings. The next n lines contain a_1, a_2, …, a_n — distinct binary strings of length m.

The total length of all given binary strings in all test cases in one test does not exceed 10^5.

Output

Print t answers to the test cases. For each test case, print a string of length m — the median of the sorted sequence of remaining strings in the corresponding test case.

Example

Input


5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10


Output


100
010
0
1
11

Note

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is [001, 010, 101, 110]. Therefore, the desired median is 010.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
#pragma warning(disable : 4996)
#pragma hdrstop
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T>
constexpr auto has_begin(int) -> decltype(std::begin(std::declval<T>()), true) {
  return true;
}
template <typename T>
constexpr bool has_begin(...) {
  return false;
}
template <typename T>
using is_container = std::integral_constant<bool, has_begin<T>(0)>;
template <typename T, typename... Types>
using is_one_of = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using is_sane_integer = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !is_one_of<typename std::remove_cv<T>::type, char, signed char,
                   unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
std::string to_string(const std::string& s) { return '"' + s + '"'; }
std::string to_string(const char* s) { return to_string(std::string(s)); }
std::string to_string(const char ch) { return {'\'', ch, '\''}; }
std::string to_string(const bool b) { return (b ? "true" : "false"); }
template <typename T,
          typename std::enable_if<Disjunction<
              is_sane_integer<T>::value,
              std::is_floating_point<T>::value>::value>::type* = nullptr>
std::string to_string(const T value) {
  return std::to_string(value);
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>&);
template <typename T,
          typename std::enable_if<is_container<T>::value>::type* = nullptr>
std::string to_string(const T& container) {
  bool is_first = true;
  std::string res = "{";
  for (const auto& x : container) {
    if (!is_first) {
      res += ", ";
    }
    is_first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>& p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
std::vector<std::string> vec_splitter(std::string s) {
  s += ',';
  std::vector<std::string> res;
  while (!s.empty()) {
    const size_t pos = s.find(',');
    res.emplace_back(s.substr(0, pos));
    s = s.substr(pos + 1);
  }
  return res;
}
void debug_out(std::vector<std::string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  std::cerr << std::endl;
}
template <typename Head, typename... Tail>
void debug_out(std::vector<std::string> args, int idx, int LINE_NUM, Head H,
               Tail... T) {
  std::stringstream ss;
  ss << to_string(H);
  if (idx > 0) {
    std::cerr << ", ";
  } else {
    std::cerr << "Line(" << LINE_NUM << ") ";
  }
  std::cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
namespace std {
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
  for (auto& it : vec) {
    in >> it;
  }
  return in;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& rhs) {
  in >> rhs.first >> rhs.second;
  return in;
}
}  // namespace std
void assign_files_input_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  using value_type = T;
  constexpr explicit IntegerIterator(const value_type value) : value_(value) {}
  IntegerIterator& operator++() {
    ++value_;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value_;
    return copy;
  }
  IntegerIterator& operator--() {
    --value_;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value_;
    return copy;
  }
  constexpr value_type operator*() const { return value_; }
  constexpr bool operator==(const IntegerIterator rhs) const {
    return value_ == rhs.value_;
  }
  constexpr bool operator!=(const IntegerIterator rhs) const {
    return !(*this == rhs);
  }
  constexpr value_type operator+(const IntegerIterator rhs) const {
    return value_ + rhs.value_;
  }
  IntegerIterator& operator+=(const IntegerIterator rhs) const {
    value_ += rhs.value_;
    return *this;
  }
  constexpr value_type operator-(const IntegerIterator rhs) const {
    return value_ - rhs.value_;
  }
  IntegerIterator& operator-=(const IntegerIterator rhs) const {
    value_ -= rhs.value_;
    return *this;
  }

 private:
  value_type value_;
};
template <typename T>
class IntegerRange {
 public:
  using const_iterator = IntegerIterator<T>;
  constexpr IntegerRange(const T begin, const T end)
      : begin_(begin), end_(end) {}
  constexpr const_iterator begin() const { return const_iterator(begin_); }
  constexpr const_iterator end() const { return const_iterator(end_); }
  constexpr T size() const { return end_ - begin_; }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedRange {
 public:
  using const_iterator = typename std::decay<T>::type::const_iterator;
  using reverse_iterator = std::reverse_iterator<const_iterator>;
  explicit constexpr ReversedRange(const T& iterable)
      : begin_(iterable.begin()), end_(iterable.end()) {}
  constexpr reverse_iterator begin() const { return reverse_iterator(end_); }
  constexpr reverse_iterator end() const { return reverse_iterator(begin_); }

 private:
  const_iterator begin_;
  const_iterator end_;
};
template <typename T>
ReversedRange<T> reversed(T&& iterable) {
  return ReversedRange<T>{iterable};
}
template <typename T>
constexpr IntegerRange<T> range(const T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
constexpr IntegerRange<T> range(const T from, const T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T from, const T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from) {
  return reversed(range(from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from, const T to) {
  return reversed(range(to, from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from) {
  return reversed(range(from + 1));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from,
                                                            const T to) {
  return reversed(range(to, from + 1));
}
template <typename R>
void sort(R& range) {
  std::sort(range.begin(), range.end());
}
template <typename R, typename Comp>
void sort(R& range, Comp comp) {
  std::sort(range.begin(), range.end(), comp);
}
template <typename R>
void reverse(R& range) {
  std::reverse(range.begin(), range.end());
}
template <typename R, typename T>
auto lower_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto lower_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value, comp);
}
template <typename R, typename T>
auto upper_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto upper_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value, comp);
}
template <typename R>
auto min_element(const R& range) -> decltype(range.begin()) {
  return std::min_element(range.begin(), range.end());
}
template <typename R>
auto max_element(const R& range) -> decltype(range.begin()) {
  return std::max_element(range.begin(), range.end());
}
template <typename R>
bool next_permutation(R& range) {
  return std::next_permutation(range.begin(), range.end());
}
template <typename T>
void unique(std::vector<T>& range) {
  range.erase(std::unique(range.begin(), range.end()), range.end());
}
template <typename T>
void dedup(std::vector<T>& range) {
  sort(range);
  unique(range);
}
template <typename R>
R sorted(R range) {
  sort(range);
  return range;
}
template <typename R, typename Comp>
R sorted(R range, Comp comp) {
  sort(range, comp);
  return range;
}
static constexpr long double PI = 3.14159265358979323846;
static constexpr long double EPS = 1e-9;
static constexpr int32_t INF = 0x3f3f3f3f;
static constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr int32_t DX[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
static constexpr int32_t DY[8] = {0, 1, 0, -1, -1, 1, 1, -1};
static constexpr uint32_t kDayMonth[12] = {31, 28, 31, 30, 31, 30,
                                           31, 31, 30, 31, 30, 31};
enum Direction : uint8_t {
  Up,
  Right,
  Down,
  Left,
  UpLeft,
  UpRight,
  DownRight,
  DownLeft,
  North = Up,
  East = Right,
  South = Down,
  West = Left,
  NorthWest = UpLeft,
  NorthEast = UpRight,
  SouthEast = DownRight,
  SouthWest = DownLeft,
  Unknown = 255
};
namespace Random {
inline std::chrono::system_clock::rep current_timestamp() {
  return std::chrono::system_clock::now().time_since_epoch().count();
}
inline uint64_t get_new_rand_seed() {
  return static_cast<uint64_t>(current_timestamp());
}
inline uint64_t get_rand_seed() {
  static const uint64_t kRandSeed = get_new_rand_seed();
  return kRandSeed;
}
using Engine = std::mt19937_64;
template <typename T>
using Distribution = std::uniform_int_distribution<T>;
inline Engine& random_engine() {
  static Engine engine(get_rand_seed());
  return engine;
}
template <typename T>
inline T get(const T to) {
  Distribution<T> distribution(0, to);
  return distribution(random_engine());
}
template <typename T>
inline T get(const T from, const T to) {
  return get(to - from) + from;
}
template <typename T = int32_t>
inline T get() {
  return get(static_cast<T>(0), std::numeric_limits<T>::max());
}
}  // namespace Random
template <typename T,
          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
class SafeIntegralHash {
 public:
  const T kRandomValue = static_cast<T>(Random::current_timestamp());
  T operator()(const T& value) const { return value ^ kRandomValue; }
};
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMap = std::unordered_map<Key, Value, SafeIntegralHash<Key>>;
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiMap =
    std::unordered_multimap<Key, Value, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedSet = std::unordered_set<Key, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiSet =
    std::unordered_multiset<Key, SafeIntegralHash<Key>>;
namespace std {
template <typename T, typename U>
struct hash<std::pair<T, U>> {
  std::size_t operator()(const std::pair<T, U>& pair) const {
    return pair.first * 877117 + pair.second;
  }
};
}  // namespace std
template <typename T, typename std::enable_if<
                          std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return abs(a) < EPS;
}
template <typename T, typename std::enable_if<
                          !std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return a == 0;
}
template <typename T>
inline bool umin(T& a, const T& b) {
  return (b < a ? a = b, true : false);
}
template <typename T>
inline bool umax(T& a, const T& b) {
  return (a < b ? a = b, true : false);
}
template <typename T, size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
template <typename T>
inline bool is_leap_year(const T year) {
  return year % 400 == 0 || (year % 100 != 0 && (year & 3) == 0);
}
inline size_t get_days_in_month(const size_t month, const size_t year) {
  return kDayMonth[month] + (month == 1 && is_leap_year(year) ? 1 : 0);
}
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pli = std::pair<ll, int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vp = std::vector<pii>;
class HDvoichnayaMediana {
 public:
  static constexpr bool kWriteCaseNumber = false;
  static constexpr bool kMultiTest = true;
  ll go(ll left, ll right, ll pos, const std::vector<ll>& a) {
    if (left + 1 == right) {
      return left;
    }
    ll med = (left + right) / 2;
    auto count = [&a](const ll left, const ll right) {
      ll ans = right - left;
      for (ll x : a) {
        if (x >= left && x < right) {
          --ans;
        }
      }
      return ans;
    };
    ll cnt_l = count(left, med);
    ll cnt_r = count(med, right);
    if (pos > cnt_l) {
      return go(med, right, pos - cnt_l, a);
    } else {
      return go(left, med, pos, a);
    }
  }
  void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    std::vector<std::string> a(n);
    in >> a;
    std::vector<ll> vals;
    for (const auto& row : a) {
      ll val = 0;
      for (char ch : row) {
        val = val * 2 + (ch - '0');
      }
      vals.emplace_back(val);
    }
    ll total = (1LL << m);
    ll left = total - n;
    42;
    ll ans = go(0, total, (left - 1) / 2 + 1, vals);
    42;
    std::string binans = "";
    while (ans > 0) {
      binans += (ans % 2) + '0';
      ans /= 2;
    }
    reverse(binans);
    binans = std::string(m - binans.length(), '0') + binans;
    out << binans << std::endl;
  }
  HDvoichnayaMediana() {}
  static constexpr bool kUseCustomChecker = false;
  bool check(std::istringstream in, std::istringstream jury,
             std::istringstream out) {
    return true;
  }
  static constexpr size_t kGeneratedTestsCount = 0;
  static constexpr bool kStopAfterFirstFail = false;
  static void generate_test(std::ostream& test) {}
};
int main() {
  HDvoichnayaMediana solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  srand(time(nullptr));
  out << std::fixed << std::setprecision(16);
  if (HDvoichnayaMediana::kMultiTest) {
    size_t tests_count;
    in >> tests_count;
    for (size_t test_id : inclusiveRange<size_t>(1, tests_count)) {
      if (HDvoichnayaMediana::kWriteCaseNumber) {
        out << "Case #" << test_id << ": ";
      }
      solver.solve(in, out);
    }
  } else {
    solver.solve(in, out);
  }
  return 0;
}

```