Problem: This is a harder version of the problem. The difference is only in constraints.

You are given a rectangular n × m matrix a. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.

After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for i-th row it is equal r_i. What is the maximal possible value of r_1+r_2+…+r_n?

Input

The first line contains an integer t (1 ≤ t ≤ 40), the number of test cases in the input.

The first line of each test case contains integers n and m (1 ≤ n ≤ 12, 1 ≤ m ≤ 2000) — the number of rows and the number of columns in the given matrix a. 

Each of the following n lines contains m integers, the elements of a (1 ≤ a_{i, j} ≤ 10^5).

Output

Print t integers: answers for all test cases in the order they are given in the input.

Example

Input


3
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7
3 3
9 9 9
1 1 1
1 1 1


Output


12
29
27

Note

In the first test case you can shift the third column down by one, this way there will be r_1 = 5 and r_2 = 7.

In the second case you can don't rotate anything at all, this way there will be r_1 = r_2 = 10 and r_3 = 9.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <typename T1, typename T2>
auto Endl(std::basic_ostream<T1, T2>& ostr)
    -> decltype(std::endl<T1, T2>(ostr)) {
  return std::endl<T1, T2>(ostr);
}
volatile bool isLocalTestEnabled = 0;
bool g_isLocalPrintEnabled = (bool)(0);
template <typename T>
void UpdateMin(T& a, const T b) {
  a = std::min(a, b);
}
template <typename T>
void UpdateMax(T& a, const T b) {
  a = std::max(a, b);
}
const long double Pi = std::atan(1.0L) * 4.0L;
static const long double Eps = 1.0e-09;
template <typename T>
bool IsEqual(const T a, const T b) {
  return std::abs(a - b) < Eps;
}
template <typename T>
bool IsGreater(const T a, const T b) {
  return a > b + Eps;
}
template <typename T>
bool IsLess(const T a, const T b) {
  return a + Eps < b;
}
template <typename T>
bool IsGreaterEqual(const T a, const T b) {
  return !IsLess(a, b);
}
template <typename T>
bool IsLessEqual(const T a, const T b) {
  return !IsGreater(a, b);
}
template <typename T>
std::string ToStr(const T& val) {
  std::ostringstream ostr;
  ostr << val;
  return ostr.str();
}
template <typename T>
bool FromStr(const std::string& str, T& val) {
  std::istringstream istr(str);
  istr >> val;
  return !!istr;
}
template <typename T>
T FromStr(const std::string& str) {
  T val = {};
  std::istringstream istr(str);
  istr >> val;
  return val;
}
template <typename ContainerType, typename ValueType>
bool Contains(const ContainerType& c, const ValueType& v) {
  return c.find(v) != c.end();
}
uint64_t SafeAdd(uint64_t a, uint64_t b) {
  uint64_t M = std::numeric_limits<uint64_t>::max();
  return a <= M - b ? a + b : M;
}
uint64_t SafeMul(uint64_t a, uint64_t b) {
  uint64_t M = std::numeric_limits<uint64_t>::max();
  return a <= M / b ? a * b : M;
}
template <typename T>
std::istream& operator>>(std::istream& ist, std::vector<T>& data) {
  ;
  for (size_t i = 0; i < data.size(); i++) {
    ist >> data[i];
  }
  return ist;
}
template <typename T>
T Read(std::istream& ist) {
  ;
  T val;
  ist >> val;
  return val;
}
template <typename T>
std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data) {
  for (size_t i = 0; i < data.size(); i++) {
    if (i != 0) {
      ost << ' ';
    }
    ost << data[i];
  }
  return ost;
}
template <size_t id>
class StopWatch {};
uint32_t Pow(const uint32_t v, const size_t n) {
  uint32_t r = 1;
  for (size_t i = 1; i <= n; i++) {
    r *= v;
  }
  return r;
}
void SplitMask3(const uint32_t mask3, const size_t limit, uint32_t& mask2a,
                uint32_t& mask2b) {
  uint32_t t = mask3;
  mask2a = 0;
  mask2b = 0;
  for (size_t i = 0; i < limit; i++) {
    const uint32_t r = t % 3;
    t /= 3;
    mask2a <<= 1;
    mask2b <<= 1;
    if (r == 1) {
      mask2a |= 1;
    } else if (r == 2) {
      mask2b |= 1;
    }
  }
}
class SumCalculator {
  const std::vector<std::vector<uint32_t> >& a;
  const size_t n;
  const size_t m;
  std::vector<std::vector<uint32_t> > delta;

 private:
  void CalculateBestSums() {
    StopWatch<2> sw;
    (void)sw;
    delta = std::move(
        std::vector<std::vector<uint32_t> >(m, std::vector<uint32_t>(1U << n)));
    for (size_t column = 0; column < m; column++) {
      for (uint32_t mask = 0; mask < (1U << n); mask++) {
        for (size_t shift = 0; shift < n; shift++) {
          UpdateMax(delta[column][mask], GetSum(column, shift, mask));
        }
      }
    }
  }
  uint32_t GetSum(const size_t column, const size_t shift,
                  const uint32_t mask) const {
    uint32_t sum = 0;
    for (size_t r = 0; r < n; r++) {
      const size_t row = (r + shift) % n;
      if (mask & (1U << row)) {
        sum += a[r][column];
      }
    }
    return sum;
  }

 public:
  SumCalculator(const std::vector<std::vector<uint32_t> >& a)
      : a(a), n(a.size()), m(a[0].size()) {
    CalculateBestSums();
  }
  uint32_t GetBestSum(const size_t column, const uint32_t mask) const {
    return delta[column][mask];
  }
};
uint32_t GetAns(const std::vector<std::vector<uint32_t> >& a) {
  const size_t n = a.size();
  const size_t m = a[0].size();
  const uint32_t MaskLimit2 = Pow(2, n);
  const SumCalculator calc(a);
  StopWatch<3> sw;
  (void)sw;
  std::vector<std::vector<uint32_t> > dp(m, std::vector<uint32_t>(MaskLimit2));
  for (uint32_t mask2 = 0; mask2 < MaskLimit2; mask2++) {
    dp[0][mask2] = calc.GetBestSum(0, mask2);
  }
  for (size_t column = 1; column < m; column++) {
    for (uint32_t newMask = 0; newMask < MaskLimit2; newMask++) {
      UpdateMax(dp[column][newMask], dp[column - 1][newMask]);
      for (uint32_t prevMask = newMask; prevMask > 0;
           prevMask = (prevMask - 1) & newMask) {
        UpdateMax(dp[column][newMask], calc.GetBestSum(column, prevMask) +
                                           dp[column - 1][newMask ^ prevMask]);
      }
    }
  }
  const uint32_t maxAns = *std::max_element(dp[m - 1].begin(), dp[m - 1].end());
  return maxAns;
}
bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode) {
  StopWatch<1> sw;
  (void)sw;
  size_t t;
  ist >> t;
  if (multipleTestMode && !ist) return false;
  if (!g_isLocalPrintEnabled) {
  } else
    std::cerr << Endl << "Next test" << Endl;
  for (size_t ti = 0; ti < t; ti++) {
    size_t n, m;
    ist >> n >> m;
    std::vector<std::vector<uint32_t> > a(n, std::vector<uint32_t>(m));
    for (size_t i = 0; i < n; i++) {
      ist >> a[i];
    }
    const auto getMaxValueInColumn = [&a](const size_t column) {
      uint32_t m = 0;
      for (size_t i = 0; i < a.size(); i++) {
        UpdateMax(m, a[i][column]);
      }
      return m;
    };
    const auto pred = [&getMaxValueInColumn](const size_t lhs,
                                             const size_t rhs) {
      const uint32_t maxL = getMaxValueInColumn(lhs);
      const uint32_t maxR = getMaxValueInColumn(rhs);
      return maxL > maxR;
    };
    std::vector<size_t> indexes(m);
    for (size_t i = 0; i < m; i++) {
      indexes[i] = i;
    }
    std::sort(indexes.begin(), indexes.end(), pred);
    if (indexes.size() > n) {
      indexes.resize(n);
    }
    std::vector<std::vector<uint32_t> > b(
        n, std::vector<uint32_t>(indexes.size()));
    for (size_t i = 0; i < n; i++) {
      for (size_t j = 0; j < indexes.size(); j++) {
        b[i][j] = a[i][indexes[j]];
      }
    }
    const uint32_t ans = GetAns(b);
    ost << ans << std::endl;
  }
  return multipleTestMode;
}
void RunSolve(std::istream& ist, std::ostream& ost) { Solve(ist, ost, false); }
int main(int argc, const char* argv[]) {
  std::ios_base::sync_with_stdio(false);
  if (argc > 1) {
    std::ifstream ifs(argv[1]);
    if (!ifs) {
      std::cout << "File not found: " << argv[1] << Endl;
      return 1;
    }
    RunSolve(ifs, std::cout);
    return 0;
  }
  RunSolve(std::cin, std::cout);
}