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;
template <typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
ostream &operator<<(ostream &s, const vector<T> &x) {
  s << "[";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "]";
  return s;
}
template <typename T>
ostream &operator<<(ostream &s, const set<T> &x) {
  s << "{";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "}";
  return s;
}
template <typename U, typename V>
ostream &operator<<(ostream &s, const pair<U, V> &x) {
  s << "(" << x.first << ", " << x.second << ")";
  return s;
}
template <typename T>
bool chmax(T &x, const T &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
const long long MOD = 1e6 + 3;
const int maxn = 1e6 + 2;
long long fact[maxn], inv[maxn];
long long binpow(long long x, long long st, long long mod) {
  long long ans = 1;
  while (st) {
    if (st & 1) {
      ans = (ans * x) % mod;
    }
    x = (x * x) % mod;
    st >>= 1;
  }
  return ans;
}
long long getc(long long n, long long k) {
  return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
vector<string> ansstr(
    {"YES", "NO",  "NO",  "YES", "NO",  "NO",  "NO",  "NO",  "NO",  "YES",
     "YES", "YES", "YES", "YES", "YES", "YES", "NO",  "YES", "NO",  "YES",
     "NO",  "NO",  "YES", "NO",  "NO",  "YES", "NO",  "NO",  "YES", "YES",
     "NO",  "YES", "NO",  "YES", "NO",  "YES", "YES", "YES", "NO",  "YES",
     "YES", "NO",  "YES", "YES", "NO",  "YES", "YES", "YES", "NO",  "YES",
     "NO",  "NO",  "YES", "YES", "YES", "YES", "YES", "YES", "NO",  "NO",
     "YES", "NO",  "NO",  "NO",  "NO",  "YES", "NO",  "NO",  "NO",  "NO",
     "YES", "NO",  "YES", "NO",  "NO",  "NO",  "YES", "YES", "NO",  "YES",
     "YES", "NO",  "NO",  "NO",  "NO",  "NO",  "NO",  "YES", "NO",  "NO",
     "YES", "NO",  "YES", "NO",  "NO",  "NO",  "NO",  "YES", "YES", "YES",
     "YES", "YES", "NO",  "NO",  "NO",  "YES", "NO",  "YES", "NO",  "YES",
     "NO",  "YES", "NO",  "NO",  "YES", "YES", "YES", "YES", "NO",  "NO",
     "NO",  "YES", "NO",  "YES", "YES", "YES", "NO",  "YES", "NO",  "NO",
     "NO",  "YES", "NO",  "NO",  "NO",  "YES", "YES", "YES", "YES", "YES",
     "YES", "YES", "YES", "YES", "YES", "YES", "NO",  "YES", "NO",  "NO",
     "NO",  "NO",  "NO",  "YES", "NO",  "NO",  "YES", "NO",  "YES", "NO",
     "YES", "NO",  "YES", "NO",  "NO",  "YES", "YES", "NO",  "NO",  "YES",
     "NO",  "NO",  "NO",  "NO",  "YES", "NO",  "YES", "NO",  "NO",  "YES",
     "NO",  "YES", "YES", "YES", "NO",  "NO",  "NO",  "YES", "YES", "NO",
     "YES", "NO",  "YES", "YES", "YES", "NO",  "YES", "YES", "NO",  "YES",
     "NO",  "YES", "YES", "NO",  "YES", "YES", "NO",  "NO",  "YES", "NO",
     "NO",  "NO",  "YES", "YES", "NO",  "YES"});
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (auto ans : ansstr) {
    cout << ans << "\n";
  }
  return 0;
}