Untitled

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll = long long;

struct State {
	int i;
	bitset<101> paints;
};

struct customSort {
	bool operator()(const State& a, const State& b)	const {
		return a.i < b.i;
	}
};

map<State, int, customSort> dp2;

int n;
vector<bitset<101>> dp;
vector<int> a;

int minUse(int i) {
	if(i == n) {
		bool psbl = true;
		for(int j = 0; j < n; j++) {
			if(dp[i-1][j] == 0) {
				psbl = false;
				break;
			}
		}
		if(psbl) return 0;
		else return 1e7;
	}
	// auto copy = dp[i];
	// if(dp2.find({i, copy}) != dp2.end()) return dp2[{i, copy}];

	// if choose left
	bitset<101> temp1 = dp[i-1];
	int left = max(0, i - a[i] + 1);
	for(int j = left; j <= i; j++) {
		temp1.set(j);
	}
	dp[i] = temp1;
	int a1 = 1 + minUse(i+1);

	bitset<101> temp2 = dp[i-1];
	int right = min(n-1, i + a[i] -1);
	for(int j = i; j <= right; j++) {
		temp2.set(j);
	}
	dp[i] = temp2;
	int a2 = 1 + minUse(i+1);

	bitset<101> temp3 = dp[i-1];
	dp[i] = temp3;
	int a3 = minUse(i+1);

	if(a1 < min(a2, a3)) {
		dp[i] = temp1;
		dp2[{i, temp1}] = a1;
	} else if (a2 < min(a1, a3)) {
		dp[i] = temp2;
		dp2[{i, temp2}] = a2;
	} else {
		dp[i] = temp3;
		dp2[{i, temp3}] = a3;
	}

	return min(a1, min(a2, a3));
}

void solve()
{
	cin >>n ;
	dp.clear();
	dp.resize(n+1, bitset<101>(n+1));
	a.clear();
	a.resize(n+1);
	for(int i = 0; i < n; ++i) cin >> a[i];
	cout << minUse(0) << endl;
}

int main()
{

	int t;
	cin >> t;

	while(t--) solve();
}