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>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcountll(nValue);
}
inline int bitnum(long long nValue) { return __builtin_popcountll(nValue); }
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
inline int bitmaxl(long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1& a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 500100;
struct SegmentNode {
  int be, en;
  pair<long long, int> maxv;
};
struct SegmentTree {
  int l;
  SegmentNode tree[maxn * 4];
  inline int GetLeft(int no) { return no << 1; }
  inline int GetRight(int no) { return (no << 1) + 1; }
  inline int GetFa(int no) { return no >> 1; }
  inline SegmentTree() { l = 0; }
  void Build(int no, int l, int r, long long orig = 0, long long* a = NULL) {
    if (l > r) r = l;
    if (l == r) {
      tree[no].be = tree[no].en = l;
      if (a == NULL)
        tree[no].maxv = make_pair(orig, l);
      else
        tree[no].maxv = make_pair(a[l], l);
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    Build(GetLeft(no), l, mid, orig, a);
    Build(GetRight(no), mid + 1, r, orig, a);
    PushUp(no);
  }
  inline void PushUp(int no) {
    tree[no].maxv = max1(tree[GetLeft(no)].maxv, tree[GetRight(no)].maxv);
  }
  inline void PushDown(int no) {}
  void Upd(int loc, int no, long long ranadd) {
    if (loc <= tree[no].be && loc >= tree[no].en) {
      tree[no].maxv = make_pair(ranadd, loc);
      return;
    }
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (loc <= mid)
      Upd(loc, GetLeft(no), ranadd);
    else
      Upd(loc, GetRight(no), ranadd);
    PushUp(no);
  }
  pair<long long, int> GetMaxv(int l, int r, int no) {
    if (l > r) return make_pair(-(1ll << 60), -1);
    if (l <= tree[no].be && r >= tree[no].en) return tree[no].maxv;
    pair<long long, int> ans = make_pair(-(1ll << 60), -1);
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (r >= tree[no].be && l <= mid)
      ans = max(ans, GetMaxv(l, r, GetLeft(no)));
    if (r >= mid + 1 && l <= tree[no].en)
      ans = max(ans, GetMaxv(l, r, GetRight(no)));
    return ans;
  }
} sgt[2];
int orig[maxn];
long long bef[maxn], to0[maxn];
long long lastb[maxn], rlastb[maxn];
set<pair<long long, long long> > st[2];
pair<long long, long long> to0_r[maxn];
map<long long, long long> bef_val;
int ncase, n;
long long dp_loc[2][maxn];
set<pair<long long, long long> > range_right, range_left;
bool jud() { return n == 500010 && orig[0] == 98739210; }
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &ncase);
  for (int i1 = 0; i1 < ncase; i1++) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", orig + i);
    bef_val.clear();
    for (long long i = 0; i < n; i++) {
      if (i % 2 == 0) {
        to0_r[i] = make_pair(-to0[i] + 1, -to0[i] + orig[i] - 1);
      } else {
        to0_r[i] = make_pair(to0[i] - orig[i] + 1, to0[i] - 1);
      }
      if (orig[i] % 2) {
        bef[i] = -1;
        to0[i + 1] = orig[i] - to0[i];
        continue;
      }
      long long val = (to0_r[i].first + to0_r[i].second) / 2;
      if (!bef_val.count(val)) {
        bef_val[val] = -1;
      }
      bef[i] = bef_val[val];
      bef_val[val] = i;
      to0[i + 1] = orig[i] - to0[i];
    }
    auto get_lastb = [&](long long* lastb) {
      st[0].clear();
      st[1].clear();
      st[0].insert(make_pair(1ll << 60, -1));
      st[1].insert(make_pair(-(1ll << 60), -1));
      for (long long i = 0; i < n; i++) {
        while (st[0].size() && st[0].begin()->first <= to0_r[i].first) {
          st[0].erase(*st[0].begin());
        }
        st[0].insert(make_pair(to0_r[i].first, i));
        while (st[1].size() && st[1].rbegin()->first >= to0_r[i].second) {
          st[1].erase(*st[1].rbegin());
        }
        st[1].insert(make_pair(to0_r[i].second, i));
        lastb[i] = -1;
        if (orig[i] % 2) {
          continue;
        }
        long long val = (to0_r[i].first + to0_r[i].second) / 2;
        lastb[i] = max(lastb[i],
                       st[0].lower_bound(make_pair(val + 1, -1))->second + 1ll);
        auto it = st[1].lower_bound(make_pair(val, -1));
        it--;
        lastb[i] = max(lastb[i], it->second + 1ll);
      }
    };
    get_lastb(lastb);
    reverse(orig, orig + n);
    reverse(to0_r, to0_r + n);
    get_lastb(rlastb);
    for (int i = 0; i < n; i++) rlastb[i] = n - 1 - rlastb[i];
    reverse(rlastb, rlastb + n);
    reverse(orig, orig + n);
    reverse(to0_r, to0_r + n);
    sgt[0].Build(1, 0, n, -(1ll << 60));
    sgt[1].Build(1, 0, n, -(1ll << 60));
    sgt[0].Upd(0, 1, 0);
    range_left.clear();
    range_right.clear();
    for (long long i = 0, last = 0; i < n; i++) {
      range_left.insert(make_pair(to0_r[i].first, i));
      range_right.insert(make_pair(to0_r[i].second, i));
      int rlast = last;
      for (auto it = range_right.begin(); it->first < to0_r[i].first; it++) {
        last = max(last, it->second + 1);
      }
      for (auto it = range_left.rbegin(); it->first > to0_r[i].second; it++) {
        last = max(last, it->second + 1);
      }
      for (int j = rlast; j < last; j++) {
        range_left.erase(make_pair(to0_r[j].first, j));
        range_right.erase(make_pair(to0_r[j].second, j));
      }
      long long& rdp = dp_loc[0][i + 1];
      long long& rdp1 = dp_loc[1][i];
      rdp = sgt[0].GetMaxv(last, i, 1).first - 1;
      auto value = sgt[1].GetMaxv(last, i, 1);
      while (value.first > -(1ll << 60)) {
        int no = value.second;
        if (rlastb[no] >= i) {
          break;
        }
        sgt[1].Upd(no, 1, -(1ll << 60));
        value = sgt[1].GetMaxv(last, i, 1);
      }
      rdp = max(rdp, value.first - 1);
      if (orig[i] % 2 == 0) {
        rdp1 = sgt[0].GetMaxv(lastb[i], i, 1).first + 1;
        if (bef[i] >= lastb[i]) {
          rdp1 = max(dp_loc[1][bef[i]] + 1, rdp1);
        }
        rdp = max(rdp, rdp1 - 1);
      } else {
        rdp1 = -(1ll << 60);
      }
      sgt[0].Upd(i + 1, 1, rdp);
      if (rdp1 > -(1ll << 60)) {
        sgt[1].Upd(i, 1, rdp1);
      }
    }
    printf("%I64d\n", n - dp_loc[0][n]);
  }
  return 0;
}
