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;
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  debug_out(H);
  cerr << " ";
  debug_out(T...);
}
template <typename T>
void debug_out(set<T> a) {
  vector<T> _a;
  for (T t : a) _a.push_back(t);
  debug_out(_a);
}
class segtree {
 public:
  struct node {
    long long lf = -(LLONG_MAX / 2);
    long long rt = LLONG_MAX / 2;
    void apply(int l, int r, pair<long long, long long> v) {
      lf = v.first;
      rt = v.second;
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.lf = max(a.lf, b.lf);
    res.rt = min(a.rt, b.rt);
    return res;
  }
  inline void push(int x, int l, int r) {}
  inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T &...t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }
  template <typename M, typename... T>
  segtree(const vector<M> &v, const T &...t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  segtree(){};
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M &...v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  template <typename... M>
  void modify(int ll, int rr, const M &...v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  int find_first_knowingly(int x, int l, int r,
                           const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr,
                 const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last_knowingly(int x, int l, int r,
                          const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr,
                const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
int tt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> sig(n);
    vector<long long> coef(n);
    int sg = 1;
    long long co = 0;
    for (int i = 0; i < n; i++) {
      sg *= -1;
      co = a[i] - co;
      sig[i] = sg;
      coef[i] = co;
    }
    const long long inf = LLONG_MAX / 2;
    segtree st(n);
    for (int i = 0; i < n; i++) {
      long long l = -inf;
      long long r = inf;
      if (sig[i] == -1) {
        r = coef[i] - 1;
      } else {
        l = 1LL - coef[i];
      }
      st.modify(i, i, make_pair(l, r));
    }
    vector<int> var(n);
    for (int i = 0; i < n; i++) {
      long long l = -inf;
      long long r = inf;
      int cur = st.find_last(0, i, [&](const segtree::node &a) {
        long long ll = max(l, a.lf);
        long long rr = min(r, a.rt);
        if (ll <= rr) {
          l = ll;
          r = rr;
          return false;
        }
        return true;
      });
      cur++;
      if ((cur == 0 && 1 > r) || cur > 0) cur++;
      var[i] = cur;
    }
    map<long long, vector<int>> make_eq;
    for (int i = 0; i < n; i++) {
      if (a[i] & 1) continue;
      long long b = (-coef[i] + a[i] / 2) / sig[i];
      make_eq[b].push_back(i);
    }
    vector<int> reac(n, -1);
    vector<int> rev_reac(n, n);
    for (int i = 0; i < n; i++) {
      if (a[i] & 1) continue;
      int cur;
      long long sp = (a[i] / 2 - coef[i]) / sig[i];
      long long l = sp;
      long long r = sp;
      cur = st.find_first(i, n - 1, [&](const segtree::node &a) {
        long long ll = max(l, a.lf);
        long long rr = min(r, a.rt);
        if (ll <= rr) {
          l = ll;
          r = rr;
          return false;
        }
        return true;
      });
      if (cur == -1) cur = n;
      cur--;
      reac[i] = cur;
      l = sp;
      r = sp;
      cur = st.find_last(0, i, [&](const segtree::node &a) {
        long long ll = max(l, a.lf);
        long long rr = min(r, a.rt);
        if (ll <= rr) {
          l = ll;
          r = rr;
          return false;
        }
        return true;
      });
      cur++;
      if ((cur == 0 && 1 > r) || cur > 0) cur++;
      rev_reac[i] = cur;
    }
    vector<int> near(n, -1);
    for (auto foo : make_eq) {
      vector<int> pos = foo.second;
      for (int i = 1; i < (int)pos.size(); i++) {
        int c = pos[i];
        int d = pos[i - 1];
        if (rev_reac[c] <= d) near[c] = d;
      }
    }
    vector<int> tree(4 * n + 4);
    function<void(int, int, int, int, int, int)> modify =
        [&](int x, int l, int r, int ll, int rr, int v) {
          if (ll <= l && r <= rr) {
            tree[x] = v;
            return;
          }
          int mid = (l + r) >> 1;
          if (mid >= ll) modify(2 * x + 1, l, mid, ll, rr, v);
          if (mid < rr) modify(2 * x + 2, mid + 1, r, ll, rr, v);
          tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
        };
    function<int(int, int, int, int, int)> get = [&](int x, int l, int r,
                                                     int ll, int rr) {
      if (ll <= l && r <= rr) {
        return tree[x];
      }
      int mid = (l + r) >> 1;
      int res = INT_MAX;
      if (mid >= ll) res = min(res, get(2 * x + 1, l, mid, ll, rr));
      if (mid < rr) res = min(res, get(2 * x + 2, mid + 1, r, ll, rr));
      return res;
    };
    vector<int> dp(n + 1);
    vector<int> sub_dp(n + 1);
    set<pair<int, int>> cur;
    multiset<int> v;
    multiset<int> c;
    if (a[0] % 2 == 0) {
      cur.insert(make_pair(reac[0], 0));
      v.insert(0);
      c.insert(0);
    }
    for (int i = 1; i <= n; i++) {
      dp[i] = get(0, 0, n, var[i - 1], i - 1) + i + 1;
      while (cur.size() && cur.begin()->first < i - 1) {
        int id = cur.begin()->second;
        v.erase(v.find(sub_dp[id] - id));
        c.erase(c.find(dp[id] - id));
        cur.erase(cur.begin());
      }
      if (cur.size()) {
        dp[i] = min(dp[i], *v.begin() + i - 1);
        dp[i] = min(dp[i], *c.begin() + i);
      }
      if (var[i - 1] == 0) {
        dp[i] = min(dp[i], i);
      }
      modify(0, 0, n, i, i, dp[i] - i);
      if (i == n) break;
      if (a[i] & 1) continue;
      sub_dp[i] = INT_MAX / 2;
      if (rev_reac[i] < i) sub_dp[i] = get(0, 0, n, rev_reac[i], i - 1) + i + 1;
      if (~near[i]) {
        int d = near[i];
        sub_dp[i] = min(sub_dp[i], sub_dp[d] + i - d - 1);
        sub_dp[i] = min(sub_dp[i], dp[d] + i - d);
      }
      if (rev_reac[i] == 0) sub_dp[i] = min(sub_dp[i], i);
      cur.insert(make_pair(reac[i], i));
      v.insert(sub_dp[i] - i);
      c.insert(dp[i] - i);
    }
    cout << dp[n] + 1 << "\n";
  }
  return 0;
}
