#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int T, n, b[maxn], a[maxn], c[maxn], f[maxn][2];
vector<int> pos;
int lb(int x) {
	return x & -x;
}

bool pd(int x) {
	return lb(x + 1) == x + 1;
}

int main() {
	// scanf("%d", &n);
	n = 100000;
	b[0] = b[1] = 1;
	int m = 2;
	while(m <= n) {
		for(int j = m - 1, k = m; j >= 0; -- j, ++ k)
			b[k] = b[j];
		b[m] = -b[m];
		m *= 2;
	}
	pos.push_back(1);
	while(pos.back() <= n)
		pos.push_back(pos.back() * 2 + 1);
	for(scanf("%d", &T); T --; ) {
		scanf("%d", &n);
		for(int i = 1; i <= n; ++ i)
			scanf("%d", &a[i]);
		// for(int i = 1; i <= n; ++ i)
			// cerr << b[i] << " ";
		// cerr << endl;
		int p = 0;
		while(pos[p] <= n)
			++ p;
		-- p;
		for(int i = 0; i <= n + 1; ++ i)
			f[i][0] = f[i][1] = 1e9;
		f[n][0] = f[n][1] = 0;
		int ans = 0;
		for(int i = n; i >= 1; -- i) {
			// cerr << i << " " << i + 1 << " " << lb(i + 1) << endl;
			if(pd(i)) { // can change
			continue;
			} else ans += (a[i] != b[i]);
		}
		printf("%d\n", ans);
	}
}