#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 5e5 + 9;
int n, a[N];

int *f[2], pl[2][N * 3];

void slv () {
  f[0] = pl[0] + N;
  f[1] = pl[1] + N;
  L (i, -n, 2 * n) {
    f[0][i] = f[1][i] = 0;
  }
  cin >> n;
  L (i, 1, n) {
    cin >> a[i];
  }
  LL ans = 0;
  int mem = 0;
  L (i, 1, n) {
    int x = a[i];
    int o = x & 1;
    for (int j = min(n, x) + 2; f[o][j]; ++j) {
      f[o][j] = 0;
    }
    for (int j = min(n, x) + 1; f[o ^ 1][j]; ++j) {
      f[o ^ 1][j] = 0;
    }
    f[o ^ 1][0] += 1 + mem;
    ++f[o];
    --f[o ^ 1];
    mem = f[o][0];
    f[o][0] = 0;
    swap(f[0], f[1]);
    ans += mem + f[0][1];
  }
  cout << ans << '\n';
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    slv();
  }
}
// I love WHQ!