Problem: The Human-Cow Confederation (HC2), led by Heidi, has built a base where people and cows can hide, guarded from zombie attacks. The entrance to the base is protected by an automated gate which performs a kind of a Turing test: it shows the entering creature a photograph and asks them whether the top and bottom halves of this photograph have been swapped or not. A person (or even a cow) will have no problem answering such questions; on the other hand, a zombie would just randomly smash one of the two buttons.

The creature is asked a series of such questions. If at least 75% of them are answered correctly, the gate is unlocked; otherwise, a side door opens, beneath which a huge fan is spinning...

Heidi is now building a robot army to fight the zombies, and she wants the robots to also be able to enter the base. You are tasked with programming them to distinguish the images.

<image>

The first two images from the test set. The first picture has been rearranged, but not the second.

Input

The first line of the input contains the number q of questions (1 ≤ q ≤ 220). After that, q questions follow, each of which in the format described below.

The first line of every question contains two space-separated integers h and w (1 ≤ h, w ≤ 600) – the height (number of rows) and width (number of columns) of the photograph. (Most photographs are roughly 200 × 300.) After this, h lines follow, each describing a single row of the picture. The picture is monochrome (in shades of grey). Its i-th row is described by w space-separated integers aij (j = 1, ..., w), where aij is the brightness of the corresponding pixel (0 ≤ aij < 256, where 0 is black and 255 is white).

Each picture will be either a real-life photograph, or a real-life photograph which has been broken up into two pieces and rearranged. More precisely, in the latter case, the topmost <image> rows have been moved to the bottom of the picture. It is guaranteed that h is even.

There is only a single input file to be processed, called all.in, and it is downloadable from the online judge. You are also a given another input file, called sample.in, which contains the first 20 pictures from all.in; you are provided the correct answers for sample.in in sample.out. You are also given a directory easy_bmp, which contains the first 50 input photographs in the form of .bmp image files, as well as a directory easy_sample_original_bmp, which contains the first 20 images before rearrangement. Check the notes for the download links.

Output

Your program should print q lines. The i-th line should contain your answer for the i-th question: YES if the photograph has been rearranged and NO otherwise. Your answers will be accepted if they all conform to this format and if at least 75% of them are correct.

Because the input is rather huge, feel free to process it locally and submit just your precomputed answers (i.e., a program which just prints your output for the input file all.in).

Note

The link to download all necessary files is http://assets.codeforces.com/files/690/easy_contestant_package.zip

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int break_point() {
  char c;
  while ((c = getchar()) != '\n')
    ;
  return 0;
}
template <typename T>
void read_integer(T &r) {
  bool sign = 0;
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c == '-') {
      sign = 1;
      break;
    }
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') break;
    r = r * 10 + (c - '0');
  }
  if (sign) r = -r;
}
long long binpowmod(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      res %= mod;
      b--;
    } else {
      a *= a;
      a %= mod;
      b >>= 1;
    }
  }
  return res;
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res *= a;
      b--;
    } else {
      a *= a;
      b >>= 1;
    }
  }
  return res;
}
inline int getbit(int x, int b) { return (x >> b) & 1; }
inline long long getbit(long long x, int b) { return (x >> b) & 1; }
inline unsigned long long getbit(unsigned long long x, int b) {
  return (x >> b) & 1;
}
inline int setbit(int x, int b) { return x | (1 << b); }
inline void _setbit(int &x, int b) { x = setbit(x, b); }
inline long long setbit(long long x, int b) { return x | (1ll << b); }
inline void _setbit(long long &x, int b) { x = setbit(x, b); }
inline int unsetbit(int x, int b) { return x & (INT_MAX - (1 << b)); }
inline void _unsetbit(int &x, int b) { x = unsetbit(x, b); }
inline int countbit(int x) {
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline long long countbit(long long x) {
  int p1 = (x >> 32) & ((1ll << 32) - 1);
  int p2 = x & ((1ll << 32) - 1);
  return countbit(p1) + countbit(p2);
}
template <typename T>
void printbit(T x, int len) {
  for (int i = len - 1; i >= 0; i--) printf("%d", getbit(x, i));
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
template <typename A, typename B>
ostream &operator<<(ostream &stream, const pair<A, B> &p) {
  stream << "{" << p.first << "," << p.second << "}";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const vector<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A, typename B>
ostream &operator<<(ostream &stream, const map<A, B> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const set<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const stack<A> &v) {
  stack<A> st = v;
  stream << "[";
  while (!st.empty()) {
    stream << st.top() << " ";
    st.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const priority_queue<A> &v) {
  priority_queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.top() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const queue<A> &v) {
  queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.front() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
void run();
int main() {
  srand(time(NULL));
  do {
    run();
    if (0) {
      0 ? printf("-------------------------------\n") : 0;
      0 ? printf("-------------------------------\n") : 0;
      0 ? break_point() : 0;
    }
  } while (0);
  return 0;
}
const int mod = 1e6 + 3;
const int N = 1003;
const int win_size = 5;
const int threshold = 50;
int matr[N][N];
int mean[2][N];
void run() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) scanf("%d", &matr[i][j]);
    for (int j = 0; j < m; j++) {
      int cnt = 0;
      int color = 0;
      for (int win_i = 0; win_i <= win_size; ++win_i)
        for (int win_j = j - win_size / 2; win_j <= j + win_size / 2; ++win_j)
          if (win_i >= 0 && win_j >= 0 && win_j < m)
            ++cnt, color += matr[win_i][win_j];
      mean[0][j] = color / cnt;
    }
    for (int j = 0; j < m; j++) {
      int cnt = 0;
      int color = 0;
      for (int win_i = n - 1; win_i >= n - 1 - win_size; --win_i)
        for (int win_j = j - win_size / 2; win_j <= j + win_size / 2; ++win_j)
          if (win_i >= 0 && win_j >= 0 && win_j < m)
            ++cnt, color += matr[win_i][win_j];
      mean[1][j] = color / cnt;
    }
    int cnt = 0;
    for (int i = 0; i < m; ++i)
      cnt += abs(mean[0][i] - mean[1][i]) <= threshold;
    printf(cnt >= m * 0.6 ? "YES\n" : "NO\n");
  }
}