#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;   }   