// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5005, P = 1e9 + 7;

int n, a[N], b[2][N], t[2], L[N], R[N], pos[N], f[N][N];

void inline clr() {
    for (int i = 0; i <= t[0]; i++) {
        for (int j = 0; j <= t[1]; j++) {
            f[i][j] = 0;
        }
    }
    t[0] = t[1] = 0;
}


void inline add(int &x, int y) {
    x += y;
    if (x >= P) x -= P;
}

int main() {
    int T; read(T);
    while (T--) {
        read(n);
        for (int i = 1; i <= n; i++) read(a[i]);
        for (int i = 1; i <= n; i++) {
            int v = a[i] & 1;
            b[v][++t[v]] = i;
            pos[i] = t[v];
        }

        for (int i = 1; i <= n; i++) {
            int v = a[i] & 1;
            L[i] = 0, R[i] = n + 1;
            for (int j = 1; j <= t[!v]; j++) {
                if (b[!v][j] < i && abs(a[b[!v][j]] - a[i]) != 1)
                    L[i] = pos[b[!v][j]];
            }
            for (int j = 1; j <= t[!v]; j++) {
                if (b[!v][j] > i && abs(a[b[!v][j]] - a[i]) != 1) {
                    R[i] = pos[b[!v][j]];
                    break;
                }
            }
        }

        f[0][0] = 1;
        for (int i = 0; i <= t[0]; i++) {
            for (int j = 0; j <= t[1]; j++) {
                if (i < t[0]) {
                    int now = b[0][i + 1];
                    if (j < R[now] && j >= L[now]) add(f[i + 1][j], f[i][j]);
                }   
                if (j < t[1]) {
                    int now = b[1][j + 1];
                    if (i < R[now] && i >= L[now]) add(f[i][j + 1], f[i][j]);
                }
            }
        }
        printf("%d\n", f[t[0]][t[1]]);
        clr();
    }
    return 0;
}

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5005, P = 1e9 + 7;

int n, a[N], b[2][N], t[2], L[N], R[N], pos[N], f[N][N];

void inline clr() {
    for (int i = 0; i <= t[0]; i++) {
        for (int j = 0; j <= t[1]; j++) {
            f[i][j] = 0;
        }
    }
    t[0] = t[1] = 0;
}


void inline add(int &x, int y) {
    x += y;
    if (x >= P) x -= P;
}

int main() {
    int T; read(T);
    while (T--) {
        read(n);
        for (int i = 1; i <= n; i++) read(a[i]);
        for (int i = 1; i <= n; i++) {
            int v = a[i] & 1;
            b[v][++t[v]] = i;
            pos[i] = t[v];
        }

        for (int i = 1; i <= n; i++) {
            int v = a[i] & 1;
            L[i] = 0, R[i] = n + 1;
            for (int j = 1; j <= t[!v]; j++) {
                if (b[!v][j] < i && abs(a[b[!v][j]] - a[i]) != 1)
                    L[i] = pos[b[!v][j]];
            }
            for (int j = 1; j <= t[!v]; j++) {
                if (b[!v][j] > i && abs(a[b[!v][j]] - a[i]) != 1) {
                    R[i] = pos[b[!v][j]];
                    break;
                }
            }
        }

        f[0][0] = 1;
        for (int i = 0; i <= t[0]; i++) {
            for (int j = 0; j <= t[1]; j++) {
                if (i < t[0]) {
                    int now = b[0][i + 1];
                    if (j < R[now] && j >= L[now]) add(f[i + 1][j], f[i][j]);
                }   
                if (j < t[1]) {
                    int now = b[1][j + 1];
                    if (i < R[now] && i >= L[now]) add(f[i][j + 1], f[i][j]);
                }
            }
        }
        printf("%d\n", f[t[0]][t[1]]);
        clr();
    }
    return 0;
}

#pragma GCC optimize(2)

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 5;

int n, k, a[N * 32], in[N * 32], rt, L = 1e9, ans[N], tot;

vector<int> g[N * 32];

int idx;

struct T{
    int l, r;
} t[N * 32];

#define ls t[p].l
#define rs t[p].r

void inline add(int x, int y) {
    if (!y) return;
    g[x].pb(y), in[y]++;                                                                   
}

void change(int &p, int l, int r, int x, int y) {
    int la = p;
    t[p = ++idx] = t[la];
    a[p] = -1;
    if (l == r) {
        add(p, y);
        add(p, la);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) change(ls, l, mid, x, y);
    else change(rs, mid + 1, r, x, y);
    if (ls) add(p, ls);
    if (rs) add(p, rs);
}

void query(int p, int l, int r, int x, int y, int i) {
    if (x > y) return ;
    if (!p) return ;
    if (x <= l && r <= y) {
        add(i, p);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) query(ls, l, mid, x, y, i);
    if (mid < y) query(rs, mid + 1, r, x, y, i);
}


priority_queue<PII, vector<PII>, greater<PII> > q;

void topo() {
    for (int i = 1; i <= idx; i++)
        if (!in[i]) q.push(mp(a[i], i));
    while (!q.empty()) {
        int u = q.top().se; q.pop(); 
        if (u <= n) ans[++tot] = a[u];
        for (int v: g[u]) {
            if (--in[v] == 0) q.push(mp(a[v], v));
        }
    }
}

int main() {
    read(n), read(k); idx = n;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = n; i; i--) {
        query(rt, 1, L, a[i] + k + 1, L, i);
        query(rt, 1, L, 1, a[i] - k - 1, i);
        change(rt, 1, L, a[i], i);
    }
    topo();
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 255, S = 1005;
int n, W, w[N], t[N];
double f[S];
bool check(double m) {
    for(int i = 1; i <= W; i++) f[i] = -2e9;
    f[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = W; ~j; j--) {
            int val = min(W, j + w[i]);
            f[val] = max(f[val], f[j] + t[i] - w[i] * m);
        }
    }
    return f[W] >= 0;
}
int main() {
    scanf("%d%d", &n, &W);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", w + i, t + i);

    double l = 0, r = 250000, eps = 1e-6;
    while(r - l > eps) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(r * 1000));
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 100005;
int n, c[N], ans = 1;
PII a[N];
void add(int x, int k){
    for(; x <= n; x += x & -x) c[x] += k;
}
int ask(int x){
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i].first), a[i].second = i;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++){
        add(a[i].second, 1);
        ans = max(ans, i - ask(i)); 
    }
    printf("%d\n", ans);
    return 0;
}

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200005;
int n, m, L[N], R[N], f[N], q[N];
int main(){

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n + 1; i++) R[i] = i - 1;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        L[b + 1] = max(L[b + 1], a);
        R[b] = min(R[b], a - 1);
    }

    for (int i = 2; i <= n + 1; i++) L[i] = max(L[i], L[i - 1]);
    for (int i = n; i; i--) R[i] = min(R[i], R[i + 1]);


    int hh = 0, tt = 0;
    q[tt] = 0;
    int j = 1;
    for (int i = 1; i <= n + 1; i++) {
        for (; j <= R[i]; j++) {
            if(f[j] == 0) continue;
            while(hh <= tt && f[q[tt]] <= f[j]) tt--;
            q[++tt] = j;
        }
        while(hh <= tt && q[hh] < L[i]) hh++;
        if(hh <= tt) f[i] = f[q[hh]] + 1;
        else f[i] = 0;
    }
    printf("%d\n", f[n + 1] - 1);
    return 0;
}

#pragma GCC optimize(3)

#include <cstdio>
#include <iostream>
#include <cstring> 
#include <algorithm>
using namespace std;
const int N = 20, S = 1005, INF = 1e9;
int n, L, D[N], C[N], ans = INF;
int a[N][S], f[1 << N];
int inline get(int x) {
    int res = 0;
    while(x)res ++, x -= x & -x;
    return res;
}
int main(){
    scanf("%d%d", &n, &L);
    for(int i = 0; i < n; i++){
        scanf("%d%d", D + i, C + i);
        for (int j = 0; j < C[i]; j++) scanf("%d", &a[i][j]);
        sort(a[i], a[i] + C[i]);
    }
    f[0] = 0;
    for (int i = 0; i < (1 << n) - 1; i++) {
        for (int j = 0; j < n; j++) {
            if(i >> j & 1) continue;
            int loc = upper_bound(a[j], a[j] + C[j], f[i]) - a[j] - 1;

            if(loc < 0) continue;   
            f[i | (1 << j)] = max(f[i | (1 << j)], max(f[i], a[j][loc] + D[j]));
        }
        if(f[i] >= L) ans = min(ans, get(i));
    }
    if(ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int S = 20, L = 305, M = 1005;

int n, K, tr[L][3], fail[L];
int cnt[L], q[L], idx, f[M][L];
char s[S];

void insert() {
    int p = 0;
    for (int i = 1; s[i]; i++) {
        int ch = s[i] - 'A';
        if (!tr[p][ch]) tr[p][ch] = ++idx;
        p = tr[p][ch];
    }
    cnt[p]++;
}

void build() {
    int hh = 0, tt = -1;
    for (int i = 0; i < 3; i++)
        if (tr[0][i]) q[++tt] = tr[0][i];
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = 0; i < 3; i++) {
            int v = tr[u][i];
            if (v) {
                fail[v] = tr[fail[u]][i];
                cnt[v] += cnt[fail[v]];
                q[++tt] = v;
            } else tr[u][i] = tr[fail[u]][i];
        }
    }
}

int main() {
    memset(f, 0xcf, sizeof f);
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        insert();
    }
    build();
    f[0][0] = 0;
    for (int i = 0; i < K; i++) {
        for (int u = 0; u <= idx; u++) {
            if (f[i][u] < 0) continue;
            for (int j = 0; j < 3; j++) {
                int v = tr[u][j];
                f[i + 1][v] = max(f[i + 1][v], f[i][u] + cnt[v]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= idx; i++) ans = max(ans, f[K][i]);
    printf("%d\n", ans);
}