#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000000;
const long long INF2 = 8000000000000000000;
const long long large_P = 1000000007;
long long my_pow(long long N, long long a, long long M) {
  long long tempo;
  if (a == 0) {
    return 1;
  } else {
    if (a % 2 == 0) {
      tempo = my_pow(N, a / 2, M);
      return (tempo * tempo) % M;
    } else {
      tempo = my_pow(N, a - 1, M);
      return (tempo * N) % M;
    }
  }
}
long long my_combination(long long N, long long a, long long M) {
  long long answer = 1;
  for (long long i = 0; i < (a); i++) {
    answer *= (N - i);
    answer %= M;
  }
  for (long long i = 0; i < (a); i++) {
    answer *= my_pow(i + 1, M - 2, M);
    answer %= M;
  }
  return answer;
}
long long my_gcd(long long& a, long long& b) {
  if (b == 0) return a;
  long long temp = a % b;
  return my_gcd(b, temp);
}
void ll_to_vector(signed base, long long n, vector<signed>& v) {
  long long tempo = n;
  long long tempo2 = n;
  signed n_digit = 1;
  while (tempo2 >= 10LL) {
    tempo2 /= 10LL;
    n_digit++;
  }
  v.assign(n_digit, 0);
  for (signed i = 0; i < n_digit; i++) {
    v.at(i) = tempo / (long long)pow(base, n_digit - 1 - i);
    tempo -= v.at(i) * (long long)pow(base, n_digit - 1 - i);
  }
}
long long char_to_int(char c) {
  switch (c) {
    case '0':
      return 0;
    case '1':
      return 1;
    case '2':
      return 2;
    case '3':
      return 3;
    case '4':
      return 4;
    case '5':
      return 5;
    case '6':
      return 6;
    case '7':
      return 7;
    case '8':
      return 8;
    case '9':
      return 9;
    default:
      return 0;
  }
}
void prime_judge(vector<bool>& prime_or_not) {
  prime_or_not.at(0) = false;
  prime_or_not.at(1) = false;
  long long n = prime_or_not.size() - 1;
  long long region = (long long)pow((long double)(n), 0.50) + 1;
  for (long long i = 2; i <= n / 2; i++) {
    prime_or_not.at(2 * i) = false;
  }
  for (long long i2 = 1; i2 < n / 2; i2++) {
    long long i = 2 * i2 + 1;
    if (i < region && prime_or_not.at(i)) {
      long long j = i * i;
      while (j < n + 1) {
        prime_or_not.at(j) = false;
        j += 2 * i;
      }
    }
  }
};
map<long long, long long> divide_to_prime(long long target) {
  map<long long, long long> res;
  long long upper_lim = ceil(pow((long double)(target), 0.50));
  vector<bool> prime_or_not(upper_lim + 1, true);
  if (upper_lim < 20) prime_or_not.assign(25, true);
  prime_judge(prime_or_not);
  long long tempo = target;
  for (long long i = 0; i < ((upper_lim + 1)); i++) {
    if (prime_or_not.at(i)) {
      while (tempo % i == 0) {
        tempo /= i;
        res[i]++;
      }
    }
  }
  if (tempo != 1) res[tempo]++;
  return res;
}
void BFS_labyrinth(queue<pair<long long, long long>>& que,
                   vector<vector<long long>>& dist, long long& area) {
  long long n = dist.size();
  long long m = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || n <= h + dh) continue;
        if (w + dw < 0 || m <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) = dist.at(h).at(w) + 1;
        que.push(make_pair(h + dh, w + dw));
      }
    }
    if (que.empty()) {
      for (long long i = 0; i < (n); i++) {
        for (long long j = 0; j < (m); j++) {
          if (dist.at(i).at(j) == -1) {
            que.push(make_pair(i, j));
            dist.at(i).at(j) = 0;
            area++;
            break;
          }
        }
        if (!que.empty()) break;
      }
    }
  }
}
void BFS01_labyrinth(deque<pair<long long, long long>>& que,
                     vector<vector<long long>>& dist,
                     vector<vector<long long>>& cost) {
  long long n = dist.size();
  long long m = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop_front();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || n <= h + dh) continue;
        if (w + dw < 0 || m <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) =
            dist.at(h).at(w) + cost.at(h + dh).at(w + dw);
        if (cost.at(h + dh).at(w + dw) == 0) {
          que.push_front(make_pair(h + dh, w + dw));
        } else {
          que.push_back(make_pair(h + dh, w + dw));
        }
      }
    }
  }
}
void dfs(const vector<vector<long long>> G, vector<bool>& seen, long long v) {
  seen.at(v) = true;
  for (long long next_v : G.at(v)) {
    if (seen.at(next_v)) continue;
    dfs(G, seen, next_v);
  }
}
class edge {
 public:
  long long to;
  long long cost;
};
void dijkstra(long long s, const vector<vector<edge>> G,
              vector<long long>& dist) {
  long long V = dist.size();
  dist.assign(V, INF);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      que;
  dist.at(s) = 0;
  que.push(make_pair(0, s));
  while (!que.empty()) {
    pair<long long, long long> p = que.top();
    que.pop();
    long long v = p.second;
    if (dist.at(v) < p.first) continue;
    for (long long i = 0; i < G.at(v).size(); i++) {
      edge e = G.at(v).at(i);
      if (dist.at(e.to) > dist.at(v) + e.cost) {
        dist.at(e.to) = dist.at(v) + e.cost;
        que.push(make_pair(dist.at(e.to), e.to));
      }
    }
  }
}
const long long Vmax2 = 1;
long long dp_warshall[Vmax2][Vmax2];
void warshall_floyd(long long V, const vector<vector<long long>> G) {
  for (long long i = 0; i < (V); i++) {
    for (long long j = 0; j < (V); j++) {
      dp_warshall[i][j] = G.at(i).at(j);
    }
  }
  for (long long k = 0; k < (V); k++) {
    for (long long i = 0; i < (V); i++) {
      for (long long j = 0; j < (V); j++) {
        dp_warshall[i][j] =
            min(dp_warshall[i][j], dp_warshall[i][k] + dp_warshall[k][j]);
      }
    }
  }
}
class UnionFind {
 public:
  vector<long long> parent;
  vector<long long> rank;
  UnionFind(long long N) : parent(N), rank(N, 0) {
    for (long long i = 0; i < (N); i++) {
      parent.at(i) = i;
    }
  }
  long long root(long long x) {
    if (parent.at(x) == x) return x;
    return parent.at(x) = root(parent.at(x));
  }
  void unite(long long x, long long y) {
    long long rx = root(x);
    long long ry = root(y);
    if (rx == ry) return;
    if (rank.at(rx) < rank.at(ry)) {
      parent.at(rx) = ry;
    } else {
      parent.at(ry) = rx;
      if (rank.at(rx) == rank.at(ry)) rank.at(rx)++;
    }
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
};
class wUnionFind {
 public:
  vector<long long> parent;
  vector<long long> diff_weight;
  vector<long long> rank;
  wUnionFind(long long N) : parent(N), diff_weight(N, 0), rank(N, 0) {
    for (long long i = 0; i < (N); i++) {
      parent.at(i) = i;
    }
  }
  long long root(long long x) {
    if (parent.at(x) == x) return x;
    long long r = root(parent.at(x));
    diff_weight.at(x) += diff_weight.at(parent.at(x));
    return parent.at(x) = r;
  }
  long long weight(long long x) {
    root(x);
    return diff_weight.at(x);
  }
  bool unite(long long x, long long y, long long w) {
    long long rx = root(x);
    long long ry = root(y);
    long long diff_weight_to_ry_from_rx = w + weight(x) - weight(y);
    if (rx == ry) return false;
    if (rank.at(rx) < rank.at(ry)) {
      parent.at(rx) = ry;
      diff_weight.at(rx) = -diff_weight_to_ry_from_rx;
    } else {
      parent.at(ry) = rx;
      diff_weight.at(ry) = diff_weight_to_ry_from_rx;
      if (rank.at(rx) == rank.at(ry)) rank.at(rx)++;
    }
    return true;
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
};
signed main() {
  long long T;
  cin >> T;
  for (long long t = 0; t < (T); t++) {
    long long n;
    cin >> n;
    vector<long long> a(n);
    long long even = 0;
    long long odd = 0;
    long long neighbor = 0;
    for (long long i = 0; i < (n); i++) {
      cin >> a.at(i);
      if (a.at(i) % 2 == 0)
        even++;
      else
        odd++;
    }
    sort(a.begin(), a.end());
    for (long long i = 0; i < (n - 1); i++) {
      if (a.at(i + 1) - a.at(i) == 1) neighbor++;
    }
    if (even % 2 == 0)
      cout << "YES" << endl;
    else {
      if (neighbor >= 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
}

### Prompt

Your task is to create a CPP solution to the following problem:

We call two numbers x and y similar if they have the same parity (the same remainder when divided by 2), or if |x-y|=1. For example, in each of the pairs (2, 6), (4, 3), (11, 7), the numbers are similar to each other, and in the pairs (1, 4), (3, 12), they are not.

You are given an array a of n (n is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array a = [11, 14, 16, 12], there is a partition into pairs (11, 12) and (14, 16). The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.

Input

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

Each test case consists of two lines.

The first line contains an even positive integer n (2 ≤ n ≤ 50) — length of array a.

The second line contains n positive integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100).

Output

For each test case print:

  * YES if the such a partition exists, 
  * NO otherwise. 



The letters in the words YES and NO can be displayed in any case.

Example

Input


7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8


Output


YES
NO
YES
YES
YES
YES
NO

Note

The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000000;
const long long INF2 = 8000000000000000000;
const long long large_P = 1000000007;
long long my_pow(long long N, long long a, long long M) {
  long long tempo;
  if (a == 0) {
    return 1;
  } else {
    if (a % 2 == 0) {
      tempo = my_pow(N, a / 2, M);
      return (tempo * tempo) % M;
    } else {
      tempo = my_pow(N, a - 1, M);
      return (tempo * N) % M;
    }
  }
}
long long my_combination(long long N, long long a, long long M) {
  long long answer = 1;
  for (long long i = 0; i < (a); i++) {
    answer *= (N - i);
    answer %= M;
  }
  for (long long i = 0; i < (a); i++) {
    answer *= my_pow(i + 1, M - 2, M);
    answer %= M;
  }
  return answer;
}
long long my_gcd(long long& a, long long& b) {
  if (b == 0) return a;
  long long temp = a % b;
  return my_gcd(b, temp);
}
void ll_to_vector(signed base, long long n, vector<signed>& v) {
  long long tempo = n;
  long long tempo2 = n;
  signed n_digit = 1;
  while (tempo2 >= 10LL) {
    tempo2 /= 10LL;
    n_digit++;
  }
  v.assign(n_digit, 0);
  for (signed i = 0; i < n_digit; i++) {
    v.at(i) = tempo / (long long)pow(base, n_digit - 1 - i);
    tempo -= v.at(i) * (long long)pow(base, n_digit - 1 - i);
  }
}
long long char_to_int(char c) {
  switch (c) {
    case '0':
      return 0;
    case '1':
      return 1;
    case '2':
      return 2;
    case '3':
      return 3;
    case '4':
      return 4;
    case '5':
      return 5;
    case '6':
      return 6;
    case '7':
      return 7;
    case '8':
      return 8;
    case '9':
      return 9;
    default:
      return 0;
  }
}
void prime_judge(vector<bool>& prime_or_not) {
  prime_or_not.at(0) = false;
  prime_or_not.at(1) = false;
  long long n = prime_or_not.size() - 1;
  long long region = (long long)pow((long double)(n), 0.50) + 1;
  for (long long i = 2; i <= n / 2; i++) {
    prime_or_not.at(2 * i) = false;
  }
  for (long long i2 = 1; i2 < n / 2; i2++) {
    long long i = 2 * i2 + 1;
    if (i < region && prime_or_not.at(i)) {
      long long j = i * i;
      while (j < n + 1) {
        prime_or_not.at(j) = false;
        j += 2 * i;
      }
    }
  }
};
map<long long, long long> divide_to_prime(long long target) {
  map<long long, long long> res;
  long long upper_lim = ceil(pow((long double)(target), 0.50));
  vector<bool> prime_or_not(upper_lim + 1, true);
  if (upper_lim < 20) prime_or_not.assign(25, true);
  prime_judge(prime_or_not);
  long long tempo = target;
  for (long long i = 0; i < ((upper_lim + 1)); i++) {
    if (prime_or_not.at(i)) {
      while (tempo % i == 0) {
        tempo /= i;
        res[i]++;
      }
    }
  }
  if (tempo != 1) res[tempo]++;
  return res;
}
void BFS_labyrinth(queue<pair<long long, long long>>& que,
                   vector<vector<long long>>& dist, long long& area) {
  long long n = dist.size();
  long long m = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || n <= h + dh) continue;
        if (w + dw < 0 || m <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) = dist.at(h).at(w) + 1;
        que.push(make_pair(h + dh, w + dw));
      }
    }
    if (que.empty()) {
      for (long long i = 0; i < (n); i++) {
        for (long long j = 0; j < (m); j++) {
          if (dist.at(i).at(j) == -1) {
            que.push(make_pair(i, j));
            dist.at(i).at(j) = 0;
            area++;
            break;
          }
        }
        if (!que.empty()) break;
      }
    }
  }
}
void BFS01_labyrinth(deque<pair<long long, long long>>& que,
                     vector<vector<long long>>& dist,
                     vector<vector<long long>>& cost) {
  long long n = dist.size();
  long long m = dist.at(0).size();
  while (!que.empty()) {
    long long h, w;
    pair<long long, long long> tempo = que.front();
    que.pop_front();
    h = tempo.first;
    w = tempo.second;
    for (long long dh = -1; dh <= 1; dh++) {
      for (long long dw = -1; dw <= 1; dw++) {
        if (h + dh < 0 || n <= h + dh) continue;
        if (w + dw < 0 || m <= w + dw) continue;
        if (dh == 0 && dw == 0) continue;
        if (dh * dw != 0) continue;
        if (dist.at(h + dh).at(w + dw) != -1) continue;
        dist.at(h + dh).at(w + dw) =
            dist.at(h).at(w) + cost.at(h + dh).at(w + dw);
        if (cost.at(h + dh).at(w + dw) == 0) {
          que.push_front(make_pair(h + dh, w + dw));
        } else {
          que.push_back(make_pair(h + dh, w + dw));
        }
      }
    }
  }
}
void dfs(const vector<vector<long long>> G, vector<bool>& seen, long long v) {
  seen.at(v) = true;
  for (long long next_v : G.at(v)) {
    if (seen.at(next_v)) continue;
    dfs(G, seen, next_v);
  }
}
class edge {
 public:
  long long to;
  long long cost;
};
void dijkstra(long long s, const vector<vector<edge>> G,
              vector<long long>& dist) {
  long long V = dist.size();
  dist.assign(V, INF);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      que;
  dist.at(s) = 0;
  que.push(make_pair(0, s));
  while (!que.empty()) {
    pair<long long, long long> p = que.top();
    que.pop();
    long long v = p.second;
    if (dist.at(v) < p.first) continue;
    for (long long i = 0; i < G.at(v).size(); i++) {
      edge e = G.at(v).at(i);
      if (dist.at(e.to) > dist.at(v) + e.cost) {
        dist.at(e.to) = dist.at(v) + e.cost;
        que.push(make_pair(dist.at(e.to), e.to));
      }
    }
  }
}
const long long Vmax2 = 1;
long long dp_warshall[Vmax2][Vmax2];
void warshall_floyd(long long V, const vector<vector<long long>> G) {
  for (long long i = 0; i < (V); i++) {
    for (long long j = 0; j < (V); j++) {
      dp_warshall[i][j] = G.at(i).at(j);
    }
  }
  for (long long k = 0; k < (V); k++) {
    for (long long i = 0; i < (V); i++) {
      for (long long j = 0; j < (V); j++) {
        dp_warshall[i][j] =
            min(dp_warshall[i][j], dp_warshall[i][k] + dp_warshall[k][j]);
      }
    }
  }
}
class UnionFind {
 public:
  vector<long long> parent;
  vector<long long> rank;
  UnionFind(long long N) : parent(N), rank(N, 0) {
    for (long long i = 0; i < (N); i++) {
      parent.at(i) = i;
    }
  }
  long long root(long long x) {
    if (parent.at(x) == x) return x;
    return parent.at(x) = root(parent.at(x));
  }
  void unite(long long x, long long y) {
    long long rx = root(x);
    long long ry = root(y);
    if (rx == ry) return;
    if (rank.at(rx) < rank.at(ry)) {
      parent.at(rx) = ry;
    } else {
      parent.at(ry) = rx;
      if (rank.at(rx) == rank.at(ry)) rank.at(rx)++;
    }
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
};
class wUnionFind {
 public:
  vector<long long> parent;
  vector<long long> diff_weight;
  vector<long long> rank;
  wUnionFind(long long N) : parent(N), diff_weight(N, 0), rank(N, 0) {
    for (long long i = 0; i < (N); i++) {
      parent.at(i) = i;
    }
  }
  long long root(long long x) {
    if (parent.at(x) == x) return x;
    long long r = root(parent.at(x));
    diff_weight.at(x) += diff_weight.at(parent.at(x));
    return parent.at(x) = r;
  }
  long long weight(long long x) {
    root(x);
    return diff_weight.at(x);
  }
  bool unite(long long x, long long y, long long w) {
    long long rx = root(x);
    long long ry = root(y);
    long long diff_weight_to_ry_from_rx = w + weight(x) - weight(y);
    if (rx == ry) return false;
    if (rank.at(rx) < rank.at(ry)) {
      parent.at(rx) = ry;
      diff_weight.at(rx) = -diff_weight_to_ry_from_rx;
    } else {
      parent.at(ry) = rx;
      diff_weight.at(ry) = diff_weight_to_ry_from_rx;
      if (rank.at(rx) == rank.at(ry)) rank.at(rx)++;
    }
    return true;
  }
  bool same(long long x, long long y) { return (root(x) == root(y)); }
};
signed main() {
  long long T;
  cin >> T;
  for (long long t = 0; t < (T); t++) {
    long long n;
    cin >> n;
    vector<long long> a(n);
    long long even = 0;
    long long odd = 0;
    long long neighbor = 0;
    for (long long i = 0; i < (n); i++) {
      cin >> a.at(i);
      if (a.at(i) % 2 == 0)
        even++;
      else
        odd++;
    }
    sort(a.begin(), a.end());
    for (long long i = 0; i < (n - 1); i++) {
      if (a.at(i + 1) - a.at(i) == 1) neighbor++;
    }
    if (even % 2 == 0)
      cout << "YES" << endl;
    else {
      if (neighbor >= 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
}

```