#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  os << '{';
  string sep;
  for (const auto &x : arr) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
struct interval_union {
  struct segment {
    mutable int64_t start, end;
    segment() {}
    segment(int64_t _start, int64_t _end) : start(_start), end(_end) {}
    bool operator<(const segment &other) const { return start < other.start; }
  };
  set<segment> segments;
  int64_t sign = 1, offset = 0;
  int size() const { return int(segments.size()); }
  bool empty() const { return segments.empty(); }
  void clear() {
    segments.clear();
    sign = 1;
    offset = 0;
  }
  bool overlaps(const segment &seg1, const segment &seg2) const {
    return max(seg1.start, seg2.start) <= min(seg1.end, seg2.end);
  }
  void transform(int64_t &x) { x = (x - offset) * sign; }
  void transform(int64_t &start, int64_t &end) {
    transform(start);
    transform(end);
    if (start > end) swap(start, end);
  }
  bool insert(segment seg) {
    if (seg.start > seg.end) return false;
    transform(seg.start, seg.end);
    if (segments.empty()) {
      segments.insert(seg);
      return true;
    }
    auto it = segments.upper_bound(seg);
    it = it == segments.begin() ? it : prev(it);
    if (it->start <= seg.start && seg.end <= it->end) return false;
    if (!overlaps(seg, *it)) it++;
    while (it != segments.end() && overlaps(seg, *it)) {
      seg.start = min(seg.start, it->start);
      seg.end = max(seg.end, it->end);
      it = segments.erase(it);
    }
    segments.insert(it, seg);
    return true;
  }
  bool insert(int64_t start, int64_t end) { return insert({start, end}); }
  bool contains(int64_t x) {
    transform(x);
    auto it = segments.upper_bound(segment(x, 0));
    if (it == segments.begin()) return false;
    it--;
    return it->start <= x && x <= it->end;
  }
  bool overlaps_segment(int64_t start, int64_t end) {
    transform(start, end);
    auto it = segments.upper_bound(segment(start, end));
    if (it != segments.end() && it->start <= end) return true;
    if (it != segments.begin()) {
      it--;
      if (it->end >= start) return true;
    }
    return false;
  }
  void print() {
    cerr << sign << ' ' << offset << endl;
    for (auto &seg : segments)
      cerr << '(' << seg.start << ' ' << seg.end << ')' << endl;
  }
};
void run_case() {
  int N;
  cin >> N;
  vector<int64_t> A(N);
  for (auto &a : A) cin >> a;
  interval_union ranges;
  int answer;
  if (A[0] % 2 == 0) {
    ranges.insert(A[0] / 2, A[0] / 2);
    answer = 1;
  } else {
    ranges.insert(1, A[0] - 1);
    answer = 2;
  }
  for (int i = 1; i < N; i++) {
    int64_t half = -1;
    if (A[i] % 2 == 0) {
      half = A[i] / 2;
      if (ranges.contains(half)) {
        ranges.clear();
        ranges.insert(half, half);
        continue;
      }
    }
    if (half >= 0 || ranges.overlaps_segment(1, A[i] - 1)) {
      if (ranges.sign > 0) {
        while (!ranges.empty() &&
               ranges.segments.rbegin()->start + ranges.offset > A[i] - 1)
          ranges.segments.erase(--ranges.segments.end());
        if (!ranges.empty() &&
            ranges.segments.rbegin()->end + ranges.offset > A[i] - 1)
          ranges.segments.rbegin()->end = A[i] - 1 - ranges.offset;
        ranges.sign *= -1;
        ranges.offset = A[i] - ranges.offset;
      } else {
        while (!ranges.empty() &&
               -ranges.segments.begin()->end + ranges.offset > A[i] - 1)
          ranges.segments.erase(ranges.segments.begin());
        if (!ranges.empty() &&
            -ranges.segments.begin()->start + ranges.offset > A[i] - 1)
          ranges.segments.begin()->start = -(A[i] - 1 - ranges.offset);
        ranges.sign *= -1;
        ranges.offset = A[i] - ranges.offset;
      }
      if (half >= 0) ranges.insert(half, half);
      ;
      answer++;
    } else {
      ranges.clear();
      ranges.insert(1, A[i] - 1);
      ;
      answer += 2;
    }
  }
  cout << answer << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  while (tests-- > 0) run_case();
}

### Prompt

Create a solution in Cpp for the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  os << '{';
  string sep;
  for (const auto &x : arr) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
struct interval_union {
  struct segment {
    mutable int64_t start, end;
    segment() {}
    segment(int64_t _start, int64_t _end) : start(_start), end(_end) {}
    bool operator<(const segment &other) const { return start < other.start; }
  };
  set<segment> segments;
  int64_t sign = 1, offset = 0;
  int size() const { return int(segments.size()); }
  bool empty() const { return segments.empty(); }
  void clear() {
    segments.clear();
    sign = 1;
    offset = 0;
  }
  bool overlaps(const segment &seg1, const segment &seg2) const {
    return max(seg1.start, seg2.start) <= min(seg1.end, seg2.end);
  }
  void transform(int64_t &x) { x = (x - offset) * sign; }
  void transform(int64_t &start, int64_t &end) {
    transform(start);
    transform(end);
    if (start > end) swap(start, end);
  }
  bool insert(segment seg) {
    if (seg.start > seg.end) return false;
    transform(seg.start, seg.end);
    if (segments.empty()) {
      segments.insert(seg);
      return true;
    }
    auto it = segments.upper_bound(seg);
    it = it == segments.begin() ? it : prev(it);
    if (it->start <= seg.start && seg.end <= it->end) return false;
    if (!overlaps(seg, *it)) it++;
    while (it != segments.end() && overlaps(seg, *it)) {
      seg.start = min(seg.start, it->start);
      seg.end = max(seg.end, it->end);
      it = segments.erase(it);
    }
    segments.insert(it, seg);
    return true;
  }
  bool insert(int64_t start, int64_t end) { return insert({start, end}); }
  bool contains(int64_t x) {
    transform(x);
    auto it = segments.upper_bound(segment(x, 0));
    if (it == segments.begin()) return false;
    it--;
    return it->start <= x && x <= it->end;
  }
  bool overlaps_segment(int64_t start, int64_t end) {
    transform(start, end);
    auto it = segments.upper_bound(segment(start, end));
    if (it != segments.end() && it->start <= end) return true;
    if (it != segments.begin()) {
      it--;
      if (it->end >= start) return true;
    }
    return false;
  }
  void print() {
    cerr << sign << ' ' << offset << endl;
    for (auto &seg : segments)
      cerr << '(' << seg.start << ' ' << seg.end << ')' << endl;
  }
};
void run_case() {
  int N;
  cin >> N;
  vector<int64_t> A(N);
  for (auto &a : A) cin >> a;
  interval_union ranges;
  int answer;
  if (A[0] % 2 == 0) {
    ranges.insert(A[0] / 2, A[0] / 2);
    answer = 1;
  } else {
    ranges.insert(1, A[0] - 1);
    answer = 2;
  }
  for (int i = 1; i < N; i++) {
    int64_t half = -1;
    if (A[i] % 2 == 0) {
      half = A[i] / 2;
      if (ranges.contains(half)) {
        ranges.clear();
        ranges.insert(half, half);
        continue;
      }
    }
    if (half >= 0 || ranges.overlaps_segment(1, A[i] - 1)) {
      if (ranges.sign > 0) {
        while (!ranges.empty() &&
               ranges.segments.rbegin()->start + ranges.offset > A[i] - 1)
          ranges.segments.erase(--ranges.segments.end());
        if (!ranges.empty() &&
            ranges.segments.rbegin()->end + ranges.offset > A[i] - 1)
          ranges.segments.rbegin()->end = A[i] - 1 - ranges.offset;
        ranges.sign *= -1;
        ranges.offset = A[i] - ranges.offset;
      } else {
        while (!ranges.empty() &&
               -ranges.segments.begin()->end + ranges.offset > A[i] - 1)
          ranges.segments.erase(ranges.segments.begin());
        if (!ranges.empty() &&
            -ranges.segments.begin()->start + ranges.offset > A[i] - 1)
          ranges.segments.begin()->start = -(A[i] - 1 - ranges.offset);
        ranges.sign *= -1;
        ranges.offset = A[i] - ranges.offset;
      }
      if (half >= 0) ranges.insert(half, half);
      ;
      answer++;
    } else {
      ranges.clear();
      ranges.insert(1, A[i] - 1);
      ;
      answer += 2;
    }
  }
  cout << answer << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  while (tests-- > 0) run_case();
}

```