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")
using namespace std;
template <typename T>
void ckmn(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void ckmx(T& a, T b) {
  a = max(a, b);
}
void rd(int& x) { scanf("%i", &x); }
void rd(long long& x) { scanf("%lld", &x); }
void rd(char* x) { scanf("%s", x); }
void rd(double& x) { scanf("%lf", &x); }
void rd(string& x) { scanf("%s", &x); }
template <typename T1, typename T2>
void rd(pair<T1, T2>& x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(vector<T>& x) {
  for (T& i : x) rd(i);
}
template <typename T, typename... A>
void rd(T& x, A&... args) {
  rd(x);
  rd(args...);
}
template <typename T>
void rd() {
  T x;
  rd(x);
  return x;
}
int ri() {
  int x;
  rd(x);
  return x;
}
template <typename T>
vector<T> rv(int n) {
  vector<T> x(n);
  rd(x);
  return x;
}
template <typename T>
void ra(T a[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]);
}
template <typename T1, typename T2>
void ra(T1 a[], T2 b[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]);
}
template <typename T1, typename T2, typename T3>
void ra(T1 a[], T2 b[], T3 c[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]), rd(c[st + i]);
}
void re(vector<int> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    rd(u, v);
    E[u].push_back(v);
    if (!dir) E[v].push_back(u);
  }
}
template <typename T>
void re(vector<pair<int, T>> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    T w;
    rd(u, v, w);
    E[u].push_back({v, w});
    if (!dir) E[v].push_back({u, w});
  }
}
const int N = 500050;
namespace Treap {
mt19937 rng(time(0));
int ls[N], rs[N], tsz, tag[N], lzy1[N], lzy2[N], val[N], dp[N], mn[N], pri[N];
void Upd1(int x, int f) {
  if (x) val[x] += f, lzy1[x] += f;
}
void Upd2(int x, int f) {
  if (x) dp[x] += f, mn[x] += f, lzy2[x] += f;
}
void Flip(int x) {
  if (x) tag[x] ^= 1, val[x] *= -1, lzy1[x] *= -1, swap(ls[x], rs[x]);
}
void Push(int x) {
  if (tag[x]) Flip(ls[x]), Flip(rs[x]), tag[x] = 0;
  Upd1(ls[x], lzy1[x]), Upd1(rs[x], lzy1[x]), lzy1[x] = 0;
  Upd2(ls[x], lzy2[x]), Upd2(rs[x], lzy2[x]), lzy2[x] = 0;
}
void Pull(int x) {
  mn[x] = dp[x];
  if (ls[x]) ckmn(mn[x], mn[ls[x]]);
  if (rs[x]) ckmn(mn[x], mn[rs[x]]);
}
void rot_l(int& c) {
  int a = rs[c], b = ls[a];
  rs[c] = b;
  ls[a] = c;
  Pull(c);
  Pull(a);
  c = a;
}
void rot_r(int& c) {
  int a = ls[c], b = rs[a];
  ls[c] = b;
  rs[a] = c;
  Pull(c);
  Pull(a);
  c = a;
}
void Split(int c, int& a, int& b, int v) {
  if (!c)
    a = b = 0;
  else {
    Push(c);
    if (val[c] <= v) {
      a = c;
      Split(rs[c], rs[a], b, v);
      Pull(a);
    } else {
      b = c;
      Split(ls[c], a, ls[b], v);
      Pull(b);
    }
  }
}
int Make(int v, int d) {
  tsz++;
  val[tsz] = v;
  dp[tsz] = mn[tsz] = d;
  pri[tsz] = rng();
  return tsz;
}
void Ins(int& c, int v, int d) {
  if (!c)
    c = Make(v, d);
  else {
    Push(c);
    if (val[c] == v) {
      ckmn(dp[c], d);
      Pull(c);
    } else if (val[c] < v) {
      Ins(rs[c], v, d);
      if (pri[rs[c]] > pri[c])
        rot_l(c);
      else
        Pull(c);
    } else {
      Ins(ls[c], v, d);
      if (pri[ls[c]] > pri[c])
        rot_r(c);
      else
        Pull(c);
    }
  }
}
int Find(int c, int v) {
  if (!c) return 1e9;
  Push(c);
  if (val[c] == v) return dp[c];
  if (val[c] < v)
    return Find(rs[c], v);
  else
    return Find(ls[c], v);
}
}  // namespace Treap
const int M = 6 * N;
const long long inf = 1e18;
int ls[M], rs[M], tsz, root[2], dprt;
long long mn[M], mx[M], lzy[M];
void Upd(int c, long long f) {
  mn[c] += f;
  mx[c] += f;
  lzy[c] += f;
}
void Push(int c) {
  Upd(ls[c], lzy[c]);
  Upd(rs[c], lzy[c]);
  lzy[c] = 0;
}
void Pull(int c) {
  mn[c] = min(mn[ls[c]], mn[rs[c]]);
  mx[c] = max(mx[ls[c]], mx[rs[c]]);
}
void Build(int& c, int ss, int se) {
  c = ++tsz;
  mn[c] = inf;
  mx[c] = -inf;
  if (ss == se) return;
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
}
void Set(int c, int ss, int se, int qi, int f) {
  if (ss == se) {
    mn[c] = mx[c] = f;
    return;
  }
  int mid = ss + se >> 1;
  Push(c);
  if (qi <= mid)
    Set(ls[c], ss, mid, qi, f);
  else
    Set(rs[c], mid + 1, se, qi, f);
  Pull(c);
}
void Add(int c, int ss, int se, int qs, int qe, int f) {
  if (qs > qe || qs > se || ss > qe) return;
  if (qs <= ss && qe >= se) {
    Upd(c, f);
    return;
  }
  int mid = ss + se >> 1;
  Push(c);
  Add(ls[c], ss, mid, qs, qe, f);
  Add(rs[c], mid + 1, se, qs, qe, f);
  Pull(c);
}
pair<long long, long long> mrg(pair<long long, long long> a,
                               pair<long long, long long> b) {
  return {min(a.first, b.first), max(a.second, b.second)};
}
pair<long long, long long> Get(int c, int ss, int se, int qs, int qe) {
  if (qs > qe || qs > se || ss > qe) return {inf, -inf};
  if (qs <= ss && qe >= se) return {mn[c], mx[c]};
  int mid = ss + se >> 1;
  Push(c);
  return mrg(Get(ls[c], ss, mid, qs, qe), Get(rs[c], mid + 1, se, qs, qe));
}
bool ok(int c0, int c1, int i, int x, long long m0, long long m1) {
  long long hi, lo;
  if (i & 1) {
    hi = min(mn[c1], m1);
    lo = max(mx[c0], m0);
  } else {
    hi = -max(mx[c0], m0);
    lo = -min(mn[c1], m1);
  }
  ckmx(lo, (long long)0);
  lo++;
  hi--;
  return (x == -1 && lo <= hi) || (lo <= x && hi >= x);
}
int Walk(int c0, int c1, int ss, int se, int i, int x, long long m0 = -inf,
         long long m1 = inf) {
  if (ss == se) return ok(c0, c1, i, x, m0, m1) ? ss : ss + 1;
  int mid = ss + se >> 1;
  Push(c0);
  Push(c1);
  if (ok(rs[c0], rs[c1], i, x, m0, m1))
    return Walk(ls[c0], ls[c1], ss, mid, i, x, max(m0, mx[rs[c0]]),
                min(m1, mn[rs[c1]]));
  else
    return Walk(rs[c0], rs[c1], mid + 1, se, i, x, m0, m1);
}
int Find(int i, int x, int n) { return Walk(root[0], root[1], 1, n, i, x); }
int a[N], dp[N];
int main() {
  for (int t = ri(); t--;) {
    int n = ri();
    ra(a, n);
    int treap = 0;
    Build(root[0], 1, n);
    Build(root[1], 1, n);
    Build(dprt, 1, n);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
      Set(dprt, 1, n, i, dp[i - 1] + 1);
      Add(dprt, 1, n, 1, i, 1);
      Set(root[i & 1], 1, n, i, 0);
      int f = i % 2 == 1 ? a[i] : -a[i];
      Add(root[0], 1, n, 1, i, f);
      Add(root[1], 1, n, 1, i, f);
      int ptr = Find(i, -1, n), hal;
      dp[i] = Get(dprt, 1, n, ptr, i).first;
      if (a[i] % 2 == 0) {
        ptr = Find(i, a[i] / 2, n);
        hal = Get(dprt, 1, n, ptr, i).first - 1;
        ckmn(hal, Treap::Find(treap, a[i] / 2));
      }
      int p, q;
      Treap::Split(treap, p, q, a[i] - 1);
      treap = p;
      Treap::Flip(treap);
      Treap::Upd1(treap, a[i]);
      Treap::Upd2(treap, 1);
      if (a[i] % 2 == 0) Treap::Ins(treap, a[i] / 2, hal);
      if (treap) ckmn(dp[i], Treap::mn[treap]);
    }
    printf("%i\n", dp[n]);
  }
  return 0;
}
