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>
#pragma comment(linker, "/stack:20000000")
using namespace std;
using namespace std::tr1;
double __begin;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else if (t1.b != t2.b)
    return t1.b < t2.b;
  else
    return t1.c < t2.c;
}
inline int bits_count(int v) {
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline int bits_count(long long v) {
  int t = v >> 32;
  int p = (v & ((1LL << 32) - 1));
  return bits_count(t) + bits_count(p);
}
unsigned int reverse_bits(register unsigned int x) {
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
  return ((x >> 16) | (x << 16));
}
inline int sign(int x) { return x > 0; }
inline bool isPowerOfTwo(int x) { return (x != 0 && (x & (x - 1)) == 0); }
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::set<T>& v);
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::map<T1, T2>& v);
template <typename T1, typename T2, typename T3>
inline std::ostream& operator<<(std::ostream& os, const triple<T1, T2, T3>& t);
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::set<T>& v) {
  bool first = true;
  os << "[";
  for (auto ii = v.begin(); ii != v.end(); ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::map<T1, T2>& v) {
  bool first = true;
  os << "[";
  for (auto ii = v.begin(); ii != v.end(); ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
  cout << endl;
}
template <typename T1, typename T2, typename T3>
inline std::ostream& operator<<(std::ostream& os, const triple<T1, T2, T3>& t) {
  return os << "(" << t.a << ", " << t.b << ", " << t.c << ")";
}
template <typename T1, typename T2>
inline pair<T1, T2> operator+(const pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  return pair<T1, T2>(p1.first + p2.first, p1.second + p2.second);
}
template <typename T1, typename T2>
inline pair<T1, T2> operator-(const pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  return pair<T1, T2>(p1.first - p2.first, p1.second - p2.second);
}
inline long long mulmod(long long x, long long n, long long _mod) {
  long long res = 0;
  while (n) {
    if (n & 1) res = (res + x) % _mod;
    x = (x + x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
char c[606][606];
int im[2][606];
int h, w;
int get(int x, int y) {
  if (x < 0) x = 0;
  if (y < 0) y = 0;
  if (x >= h) x = h - 1;
  if (y >= w) y = w - 1;
  return c[x][y];
}
int main() {
  cout << "YES\nNO\nNO\nYES\nNO\nNO\nNO\nNO\nNO\nYES\nYES\nYES\nYES\nYES\nNO\nY"
          "ES\nNO\nYES\nNO\nYES\nNO\nNO\nNO\nNO\nNO\nYES\nNO\nNO\nYES\nYES\nNO"
          "\nYES\nNO\nYES\nNO\nNO\nYES\nYES\nNO\nNO\nYES\nNO\nYES\nYES\nNO\nYES"
          "\nYES\nNO\nNO\nYES\nNO\nNO\nYES\nYES\nYES\nYES\nYES\nYES\nNO\nNO\nYE"
          "S\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nYES\nNO\nYES\nNO\nNO\nNO\nYES"
          "\nYES\nNO\nNO\nYES\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nYES\nNO\nNO"
          "\nNO\nNO\nNO\nNO\nYES\nYES\nYES\nNO\nYES\nNO\nNO\nNO\nYES\nNO\nYES\n"
          "NO\nYES\nNO\nYES\nNO\nNO\nYES\nYES\nYES\nYES\nNO\nNO\nNO\nYES\nNO\nY"
          "ES\nYES\nYES\nNO\nYES\nNO\nNO\nNO\nYES\nNO\nNO\nNO\nYES\nNO\nNO\nNO"
          "\nYES\nYES\nYES\nYES\nNO\nYES\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nN"
          "O\nNO\nYES\nNO\nYES\nNO\nYES\nNO\nYES\nNO\nNO\nYES\nNO\nNO\nNO\nYES"
          "\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nNO\nYES\nYES\nNO\nNO\nNO\nNO\n"
          "NO\nYES\nYES\nNO\nYES\nNO\nYES\nYES\nNO\nNO\nYES\nYES\nNO\nNO\nNO\nY"
          "ES\nYES\nNO\nYES\nYES\nNO\nNO\nYES\nNO\nNO\nNO\nYES\nYES\nNO\nYES"
       << endl;
  return 0;
  freopen("easy_contestant_package/all.in", "rt", stdin);
  int q;
  cin >> q;
  int tot = 0;
  while (q--) {
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        int x;
        cin >> x;
        c[i][j] = x;
      }
    }
    int t = h / 2 - 1;
    int sum = 0;
    for (int j = 0; j < w; ++j) {
      im[0][j] = get(t, j - 1) + get(t, j) * 2 + get(t, j + 1) +
                 -get(t + 1, j - 1) - get(t + 1, j) * 2 - get(t + 1, j + 1);
      sum += abs(im[0][j]) > 0.2 * 255 * 4;
    }
    string ans = "NO";
    if (abs(sum) > w / 3) {
      ans = "YES";
    }
    cout << ans << "\\n";
  }
  std::cerr << "tot"
            << "=" << (tot) << "\n";
  return 0;
}