One day, BThero decided to play around with arrays and came up with the following problem:

You are given an array a, which consists of n positive integers. The array is numerated 1 through n. You execute the following procedure exactly once:

  * You create a new array b which consists of 2n positive integers, where for each 1 ≤ i ≤ n the condition b_{2i-1}+b_{2i} = a_i holds. For example, for the array a = [6, 8, 2] you can create b = [2, 4, 4, 4, 1, 1]. 
  * You merge consecutive equal numbers in b. For example, b = [2, 4, 4, 4, 1, 1] becomes b = [2, 4, 1]. 



Find and print the minimum possible value of |b| (size of b) which can be achieved at the end of the procedure. It can be shown that under the given constraints there is at least one way to construct b.

Input

The first line of the input file contains a single integer T (1 ≤ T ≤ 5 ⋅ 10^5) denoting the number of test cases. The description of T test cases follows.

The first line of each test contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n space-separated integers a_1, a_2, ..., a_n (2 ≤ a_i ≤ 10^9).

It is guaranteed that ∑{n} over all test cases does not exceed 5 ⋅ 10^5.

Output

For each test case, print a single line containing one integer — the minimum possible value of |b|.

Example

Input


3
3
6 8 2
1
4
3
5 6 6


Output


3
1
2
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,mmx,avx")
using namespace std;
const int MOD = 1000000007;
const int INF = 1 << 30;
const int UNDEF = INF;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
template <typename T>
int bins(vector<T> &v, T key) {
  int imin = 0, imax = (int)v.size();
  while (imin < imax) {
    int imid = (imin + imax) >> 1;
    if (v[imid] < key)
      imin = imid + 1;
    else
      imax = imid;
  }
  return imin;
}
template <typename T>
void makeunique(vector<T> &vx) {
  sort(vx.begin(), vx.end());
  auto it = unique(vx.begin(), vx.end());
  vx.resize(std::distance(vx.begin(), it));
}
template <typename Key>
class PreSet {
 public:
  vector<Key> vkey;
  void addKey(Key key) { vkey.push_back(key); }
  void buildKeys() { makeunique(vkey); }
  int getFirstGeq(Key key) { return bins(vkey, key); }
  int getLastLeq(Key key) {
    int pos = bins(vkey, key);
    if (pos == vkey.size() || vkey[pos] > key) --pos;
    return pos;
  }
  int size() { return vkey.size(); }
};
const int mn = (5e5) + 4;
using STV = int;
struct STD {
  STD() {}
  STD(int _ts, int _force, int _add) : ts(_ts), force(_force), add(_add) {}
  int ts;
  int force;
  int add;
};
template <typename Key>
class SegTree {
 public:
  STV modifyOperation(STV x, STD y) {
    int ans = x + y.add;
    if (y.force != UNDEF) chkmin(ans, y.force);
    return ans;
  }
  STV queryOperation(STV l, STV r) { return min(l, r); }
  STD deltaEffectOnSegment(STD delta, int segmentLength) { return delta; }
  STD initNeutralDelta() { return STD(-1, UNDEF, 0); }
  bool isNeutralDelta(STD delta) { return delta.ts == -1; }
  STV getInitValue(int i) { return 0; }
  STV getNeutralValue() { return INT_MAX; }
  STD joinDeltas(STD x, STD y) {
    if (x.ts > y.ts) swap(x, y);
    int maxts = y.ts;
    int force = UNDEF;
    if (y.force != UNDEF) chkmin(force, y.force);
    if (x.force != UNDEF) chkmin(force, x.force + y.add);
    return STD(maxts, force, x.add + y.add);
  }
  STD _cache_neutral_delta;
  STD getNeutralDelta() { return _cache_neutral_delta; }
  STV *value;
  STD *delta;
  int segn;
  STV joinValueWithDelta(STV value, STD delta) {
    if (isNeutralDelta(delta)) return value;
    return modifyOperation(value, delta);
  }
  void pushDelta(int root, int left, int right) {
    value[root] = joinValueWithDelta(
        value[root], deltaEffectOnSegment(delta[root], right - left + 1));
    delta[2 * root + 1] = joinDeltas(delta[2 * root + 1], delta[root]);
    delta[2 * root + 2] = joinDeltas(delta[2 * root + 2], delta[root]);
    delta[root] = getNeutralDelta();
  }
  PreSet<Key> preset;
  void addKey(Key key) { preset.addKey(key); }
  SegTree() {}
  void init() {
    preset.buildKeys();
    int n = preset.size();
    _cache_neutral_delta = initNeutralDelta();
    segn = n;
    value = new STV[4 * n];
    delta = new STD[4 * n];
    initR(0, 0, n - 1);
  }
  void initR(int root, int left, int right) {
    if (left == right) {
      value[root] = getInitValue(left);
      delta[root] = getNeutralDelta();
    } else {
      int mid = (left + right) >> 1;
      initR(2 * root + 1, left, mid);
      initR(2 * root + 2, mid + 1, right);
      value[root] = queryOperation(value[2 * root + 1], value[2 * root + 2]);
      delta[root] = getNeutralDelta();
    }
  }
  STV query(int from, int to) {
    if (from > to) return getNeutralValue();
    int n = segn;
    return query(from, to, 0, 0, n - 1);
  }
  STV query(int from, int to, int root, int left, int right) {
    if (from == left && to == right)
      return joinValueWithDelta(
          value[root], deltaEffectOnSegment(delta[root], right - left + 1));
    pushDelta(root, left, right);
    int mid = (left + right) >> 1;
    if (from <= mid && to > mid)
      return queryOperation(
          query(from, min(to, mid), root * 2 + 1, left, mid),
          query(max(from, mid + 1), to, root * 2 + 2, mid + 1, right));
    else if (from <= mid)
      return query(from, min(to, mid), root * 2 + 1, left, mid);
    else if (to > mid)
      return query(max(from, mid + 1), to, root * 2 + 2, mid + 1, right);
    else
      assert(0);
  }
  void modify(int from, int to, STD delta) {
    if (from > to) return;
    modify(from, to, delta, 0, 0, segn - 1);
  }
  void modify(int from, int to, STD delta, int root, int left, int right) {
    if (from == left && to == right) {
      this->delta[root] = joinDeltas(this->delta[root], delta);
      return;
    }
    pushDelta(root, left, right);
    int mid = (left + right) >> 1;
    if (from <= mid) modify(from, min(to, mid), delta, 2 * root + 1, left, mid);
    if (to > mid)
      modify(max(from, mid + 1), to, delta, 2 * root + 2, mid + 1, right);
    value[root] = queryOperation(
        joinValueWithDelta(
            value[2 * root + 1],
            deltaEffectOnSegment(this->delta[2 * root + 1], mid - left + 1)),
        joinValueWithDelta(
            value[2 * root + 2],
            deltaEffectOnSegment(this->delta[2 * root + 2], right - mid)));
  }
  STV queryKey(Key const &from, Key const &to) {
    return query(preset.getFirstGeq(from), preset.getLastLeq(to));
  }
  void modifyKey(Key const &from, Key const &to, STD const &delta) {
    modify(preset.getFirstGeq(from), preset.getLastLeq(to), delta);
  }
};
int a[mn];
int n;
long long c[mn];
long long vlo[mn], vhi[mn], vhalf[mn];
void go() {
  n = rint();
  for (int p = 1; p <= n; p++) a[p] = rint();
  {
    c[1] = 0;
    for (int p = 2; p <= n; p++) {
      c[p] = a[p - 1] - c[p - 1];
    }
    for (int p = 1; p <= n; p++) {
      long long lo, hi;
      long long half = LLONG_MAX;
      if (p & 1) {
        lo = 1 - c[p];
        hi = (a[p] - 1) - c[p];
        if (a[p] % 2 == 0) {
          half = a[p] / 2 - c[p];
        }
      } else {
        hi = c[p] - 1;
        lo = c[p] - (a[p] - 1);
        if (a[p] % 2 == 0) {
          half = c[p] - a[p] / 2;
        }
      }
      assert(lo <= hi);
      if (half != LLONG_MAX && (lo <= half && half <= hi)) {
        vhalf[p] = half;
      } else {
        vhalf[p] = LLONG_MAX;
      }
      vlo[p] = lo;
      vhi[p] = hi;
    }
  }
  SegTree<long long> seg;
  for (int p = 1; p <= n; p++) {
    long long half = vhalf[p];
    if (half != LLONG_MAX) seg.addKey(half);
    seg.addKey(vlo[p]);
    seg.addKey(vhi[p]);
  }
  seg.init();
  int ts = 0;
  for (int p = 1; p <= n; p++) {
    seg.modify(0, seg.segn - 1, STD(ts++, INF, 2));
    seg.modifyKey(vlo[p], vhi[p], STD(ts++, INF, -1));
    long long half = vhalf[p];
    if (half != LLONG_MAX) {
      seg.modifyKey(half, half, STD(ts++, INF, -1));
    }
    int cand = seg.query(0, seg.segn - 1);
    seg.modify(0, seg.segn - 1, STD(ts++, cand + 1, 0));
  }
  printf("%d\n", seg.query(0, seg.segn - 1) + 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = rint();
  for (int i = 0; i < t; i++) go();
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
