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>
clock_t t = clock();
namespace my_std {
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
inline T rnd(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T &t) {
  t = 0;
  char f = 0, ch = getchar();
  double d = 0.1;
  while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
  while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
  if (ch == '.') {
    ch = getchar();
    while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
  }
  t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
char __sr[1 << 21], __z[20];
int __C = -1, __zz = 0;
inline void Ot() { fwrite(__sr, 1, __C + 1, stdout), __C = -1; }
inline void print(register int x) {
  if (__C > 1 << 20) Ot();
  if (x < 0) __sr[++__C] = '-', x = -x;
  while (__z[++__zz] = x % 10 + 48, x /= 10)
    ;
  while (__sr[++__C] = __z[__zz], --__zz)
    ;
  __sr[++__C] = '\n';
}
void file() {}
inline void chktime() {}
long long ksm(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
}  // namespace my_std
using namespace my_std;
int n;
int a[505050];
namespace BIT {
int tr[505050];
void add(int x, int w) {
  ++x;
  x = n - x + 2;
  while (x <= n + 1) chkmax(tr[x], w), x += x & -x;
}
int query(int x) {
  ++x;
  x = n - x + 2;
  int res = -1e9;
  while (x) chkmax(res, tr[x]), x -= x & -x;
  return res;
}
void clear() {
  for (int i = (1); i <= (n + 1); i++) tr[i] = -1e9;
}
}  // namespace BIT
struct hh {
  int k;
  long long b;
  int l, r;
  const int q(long long x) const {
    x = x * k + b;
    return max(1ll * l, min(x, 1ll * r));
  }
  const hh operator+(const hh &x) const {
    hh res;
    res.k = k * x.k, res.b = b * x.k + x.b;
    long long L = x.q(l), R = x.q(r);
    if (L > R) swap(L, R);
    res.l = L, res.r = R;
    return res;
  }
};
struct hhh {
  hh a, b;
  int tp;
  const hhh operator+(const hhh &x) {
    return tp ? (hhh){a + x.b, b + x.a, x.tp ^ 1}
              : (hhh){a + x.a, b + x.b, x.tp};
  }
  pair<long long, long long> q(long long l, long long r) {
    return tp ? make_pair(b.q(r), a.q(l)) : make_pair(a.q(l), b.q(r));
  }
};
hhh tr[505050 << 2];
void pushup(int k) { tr[k] = tr[k << 1 | 1] + tr[k << 1]; }
void build(int k, int l, int r) {
  if (l == r)
    return tr[k] =
               (hhh){(hh){-1, a[l], 0, a[l] - 1}, (hh){-1, a[l], 1, a[l]}, 1},
           void();
  int mid = (l + r) >> 1;
  build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r), pushup(k);
}
int query(int k, int l, int r, int x, long long &L, long long &R) {
  if (r <= x) {
    pair<long long, long long> xx = tr[k].q(L, R);
    if (xx.first <= xx.second) return tie(L, R) = xx, l;
    if (l == r) return L = R = -1, l + 1;
    int mid = (l + r) >> 1;
    int res = query(k << 1 | 1, mid + 1, r, x, L, R);
    return L == -1 ? res : query(k << 1, l, mid, x, L, R);
  }
  int mid = (l + r) >> 1;
  if (x <= mid) return query(k << 1, l, mid, x, L, R);
  int res = query(k << 1 | 1, mid + 1, r, x, L, R);
  return L == -1 ? res : query(k << 1, l, mid, x, L, R);
}
int qL(int x, long long l, long long r) { return query(1, 1, n, x, l, r); }
int dp[505050];
namespace Q2 {
long long dB;
int tp;
map<long long, int> w;
multiset<int> s;
void clear() {
  dB = 0, tp = 1;
  w.clear(), s.clear();
}
void insert(long long B, int W) {
  B = (B - dB) * tp;
  if (w.find(B) == w.end())
    w[B] = W, s.insert(W);
  else if (w[B] < W)
    s.erase(s.find(w[B])), s.insert(W), w[B] = W;
}
void maintain(long long a) {
  tp *= -1, dB = a - dB;
  for (auto it = w.begin(); it != w.end();) {
    long long b = it->first * tp + dB;
    if (b < 1 || b >= a)
      s.erase(s.find(it->second)), w.erase(it++);
    else
      break;
  }
  int c = 0;
  for (auto it = w.rbegin(); it != w.rend();) {
    long long b = it->first * tp + dB;
    if (b < 1 || b >= a)
      s.erase(s.find(it->second)), it++, c++;
    else
      break;
  }
  while (c--) w.erase(prev(w.end()));
}
void add(long long B) {
  B = (B - dB) * tp;
  auto it = w.find(B);
  if (it == w.end()) return;
  s.erase(s.find(it->second)), s.insert(it->second + 1);
  ++w[B];
}
int mx() { return s.size() ? *(s.rbegin()) : -1e9; }
}  // namespace Q2
void work() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  BIT::clear();
  Q2::clear();
  BIT::add(0, 0);
  build(1, 1, n);
  for (int i = (1); i <= (n); i++) {
    int p = qL(i, 1, a[i] - 1);
    dp[i] = BIT::query(p - 1) + i - 1;
    Q2::maintain(a[i]);
    if (a[i] % 2 == 0) Q2::add(a[i] / 2);
    chkmax(dp[i], Q2::mx() + i - 1);
    if (a[i] % 2 == 0) {
      p = qL(i, a[i] / 2, a[i] / 2);
      int w = BIT::query(p - 1) + 1;
      chkmax(dp[i], w + i - 1);
      Q2::insert(a[i] / 2, w);
    }
    BIT::add(i, dp[i] - i);
  }
  print(n + n - dp[n]);
}
int main() {
  file();
  int T;
  read(T);
  while (T--) work();
  Ot();
  return 0;
}
