#include <iostream>
#include <vector>

using namespace std;

const int N = 3e5 + 7, INF = 1e9 + 7;

int a[N];
bool luat[N];
int n, ans(INF);

int dp[N];

vector < int > ord;

void bkt(int p) {
//    if (ord.size() != p) {
//        cout << "ERROR\n" << p << ": ";
//        for (int i : ord)
//            cout << i << ' ';
//        cout << '\n';
//    }
    ans = min(ans, n - p);
//    if (n - p == 2) {
//        cout << n << " - " << p << " == 2:\n";
//        for (int i : ord)
//            cout << i << ' ';
//        cout << '\n';
//    }
    for (int i = 2; i <= n; ++i) {
        if (luat[i])
            continue;
        int left(0), right(0);
        for (int j = i - 1; j >= 1; --j) {
            if (!luat[j]) {
                left = a[j];
                break;
            }
        }
        for (int j = i + 1; j <= n; ++j) {
            if (!luat[j]) {
                right = a[j];
                break;
            }
        }
        if (left && right && a[i] * 2 == left + right) {
            luat[i] = 1;
            ord.push_back(i);
            bkt(p + 1);
            luat[i] = 0;
            ord.pop_back();
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ans = INF;
        int maxim(0);
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i], maxim = max(maxim, a[i]);
        if (n <= 15) {
            bkt(0);
            cout << ans << '\n';
            continue;
        }
        if (maxim <= 3) {
            int j(0);
            for (int i = 1; i <= n; ++i) {
                if (a[i] == a[j]) {
                    if (j && a[j] == a[j - 1])
                        continue;
                    a[++j] = a[i];
                    continue;
                }
                if (j && a[j] == 2 && a[i] + a[j - 1] == 4) {
                    a[j] = a[i];
                    continue;
                }
                a[++j] = a[i];
            }
            cout << j << '\n';
            continue;
        }
        //if (a[i] == i oricare i)
        dp[2] = 2;
        for (int i = 2; i <= (n + 1) / 2; ++i)
            dp[2 * i - 1] = dp[i], dp[2 * i] = dp[i] + 1;
        cout << dp[n] << '\n';
    }
}
/*
12
2
1 2
3
1 2 3
4
1 2 3 4
5
1 2 3 4 5
6
1 2 3 4 5 6
7
1 2 3 4 5 6 7
8
1 2 3 4 5 6 7 8
9
1 2 3 4 5 6 7 8 9
10
1 2 3 4 5 6 7 8 9 10
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


*/