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;
void enable_comma() {}
string tostring(char c);
string tostring(long long x);
template <class A, class B>
string tostring(pair<A, B> p);
template <class A>
string tostring(vector<A> v);
string tostring(char c) {
  string s = "";
  s += c;
  return s;
}
string tostring(string s) { return "\"" + s + "\""; }
string tostring(char *c) { return tostring((string)c); }
string tostring(long long x) {
  if (x < 0) return "-" + tostring(-x);
  if (x > 9)
    return tostring(x / 10) + tostring(char('0' + x % 10));
  else
    return tostring(char('0' + x));
}
string tostring(int x) { return tostring((long long)x); }
string tostring(unsigned long long x) {
  if (x > 9)
    return tostring((long long)(x / 10)) + tostring(char('0' + x % 10));
  else
    return tostring(char('0' + x));
}
string tostring(unsigned x) { return tostring((long long)x); }
string tostring(double x) {
  static char res[114];
  sprintf(res, "%lf", x);
  return tostring(res);
}
string tostring(long double x) { return tostring((double)x); }
template <class A, class B>
string tostring(pair<A, B> p) {
  return "(" + tostring(p.first) + "," + tostring(p.second) + ")";
}
template <class A>
string tostring(vector<A> v) {
  string res = "{";
  for (int i = (0); i <= ((int)v.size() - 1); i++) {
    res += tostring(v[i]);
    res += i == (int)v.size() - 1 ? "}" : ",";
  }
  if (res == "{") res += "}";
  return res;
}
template <class A>
string tostring(A a, int L, int R) {
  string res = "{";
  for (int i = (L); i <= (R); i++) {
    res += tostring(a[i]);
    res += i == R ? "}" : ",";
  }
  if (res == "{") res += "}";
  return res;
}
string tostrings() { return ""; }
template <typename Head, typename... Tail>
string tostrings(Head H, Tail... T) {
  return tostring(H) + " " + tostrings(T...);
}
long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
template <class T>
void ckmax(T &x, const T y) {
  if (x < y) x = y;
}
template <class T>
void ckmin(T &x, const T y) {
  if (x > y) x = y;
}
const int N = 500005 * 2, INF = 1e9;
int n;
int ans;
long long a[N];
long long k[N], b[N];
long long calc(int i, long long v) { return k[i] * v + b[i]; }
set<long long> S;
int findlr(int i, long long L, long long R) {
  L = calc(i, L), R = calc(i, R);
  if (L > R) swap(L, R);
  auto it = S.lower_bound(L);
  return it != S.end() && *it <= R;
}
void only_save(int i, long long L, long long R) {
  L = calc(i, L), R = calc(i, R);
  if (L > R) swap(L, R);
  while (!S.empty() && *S.begin() < L) S.erase(S.begin());
  while (!S.empty() && *prev(S.end()) > R) S.erase(prev(S.end()));
}
void reget(int i, long long &mi, long long &mx) {
  mi = 1, mx = a[i] - 1;
  if (a[i] % 2 == 0) mi = mx = a[i] / 2, ans--;
}
void trans(int i, long long &mi, long long &mx) {
  enable_comma();
  if (a[i] > mi) {
    long long tmi = max(1LL, a[i] - mx);
    long long tmx = a[i] - mi;
    mi = tmi, mx = tmx;
  } else
    mi = INF;
}
void solve() {
  n = read();
  for (int i = (1); i <= (n); i++) a[i] = read();
  k[n + 1] = 1, b[n + 1] = 0;
  for (int i = (n); i >= (1); i--) {
    k[i] = -k[i + 1];
    b[i] = k[i + 1] * a[i] + b[i + 1];
  }
  ans = n * 2;
  long long mi, mx;
  reget(1, mi, mx);
  S.clear();
  for (int i = (2); i <= (n); i++) {
    if (a[i] % 2 == 1) {
      int nowv = 0;
      ckmax(nowv, (int)(a[i] > mi));
      ckmax(nowv, findlr(i, 1, a[i] - 1));
      ans -= nowv;
      if (nowv == 0) {
        S.clear();
        reget(i, mi, mx);
      } else {
        trans(i, mi, mx);
        only_save(i, 1, a[i] - 1);
      }
    } else {
      int nowv = 0;
      long long half = a[i] / 2;
      ckmax(nowv, 1 + (mi <= half && half <= mx));
      ckmax(nowv, 1 + (findlr(i, half, half)));
      enable_comma();
      (!(nowv == 1 || nowv == 2) ? cout << "Assertion failed!" << endl
                                        << "function: " << __FUNCTION__ << endl
                                        << "line: " << 215 << endl
                                        << "expression: "
                                        << "nowv == 1 || nowv == 2" << endl,
       exit(3), 0 : 1);
      ans -= nowv;
      if (nowv == 1) {
        trans(i, mi, mx);
        only_save(i, 1, a[i] - 1);
        S.insert(calc(i, half));
      } else {
        if (mi <= half && half <= mx)
          mi = mx = half;
        else
          mi = INF;
        only_save(i, half, half);
      }
    }
  }
  printf("%d\n", ans);
}
int main() {
  int T = read();
  while (T--) solve();
  return 0;
}
