Problem: Gildong is now developing a puzzle game. The puzzle consists of n platforms numbered from 1 to n. The player plays the game as a character that can stand on each platform and the goal of the game is to move the character from the 1-st platform to the n-th platform.

The i-th platform is labeled with an integer a_i (0 ≤ a_i ≤ n-i). When the character is standing on the i-th platform, the player can move the character to any of the j-th platforms where i+1 ≤ j ≤ i+a_i. If the character is on the i-th platform where a_i=0 and i ≠ n, the player loses the game.

Since Gildong thinks the current game is not hard enough, he wants to make it even harder. He wants to change some (possibly zero) labels to 0 so that there remains exactly one way to win. He wants to modify the game as little as possible, so he's asking you to find the minimum number of platforms that should have their labels changed. Two ways are different if and only if there exists a platform the character gets to in one way but not in the other way.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 500).

Each test case contains two lines. The first line of each test case consists of an integer n (2 ≤ n ≤ 3000) — the number of platforms of the game.

The second line of each test case contains n integers. The i-th integer is a_i (0 ≤ a_i ≤ n-i) — the integer of the i-th platform.

It is guaranteed that: 

  * For each test case, there is at least one way to win initially. 
  * The sum of n in all test cases doesn't exceed 3000. 

Output

For each test case, print one integer — the minimum number of different labels that should be changed to 0 so that there remains exactly one way to win.

Example

Input


3
4
1 1 1 0
5
4 3 2 1 0
9
4 1 4 2 1 0 2 1 0


Output


0
3
2

Note

In the first case, the player can only move to the next platform until they get to the 4-th platform. Since there is already only one way to win, the answer is zero.

In the second case, Gildong can change a_2, a_3, and a_4 to 0 so that the game becomes 4 0 0 0 0. Now the only way the player can win is to move directly from the 1-st platform to the 5-th platform.

In the third case, Gildong can change a_2 and a_8 to 0, then the only way to win is to move in the following way: 1 – 3 – 7 – 9.

Solution (in CPP):

Solution:
/*
"0000000000000000000000000010101111110100000000000000000000000000",
"0000000000000000000000101110101010010111110000000000000000000000",
"0000000000000000000011101000100011010000100100000000000000000000",
"0000000000000000011110101011111000011110101110100000000000000000",
"0000000000000000110000001010000011110000101010110000000000000000",
"0000000000000010011011111011101110100101100010010100000000000000",
"0000000000000111001001000000101000111100110110110110000000000000",
"0000000000011111101101101110111011100001100100100011100000000000",
"0000000000111111111111000010000010001011001101101001110000000000",
"0000000001111111111111111111101111111001111001111111111000000000",
"0000000011111111111111111111111111111111111111111111111100000000",
"0000000111111111111111111111111111111111111111111111111110000000",
"0000000111111111111111111111111111111111111111111111111110000000",
"0000001111111111111111111111111111111111111111111111111111000000",
"0000011111111111111111111111111111111111111111111111111111100000",
"0000011111111111111111111111111111111111111111111111111111100000",
"0000111111111111111111111111111111111111111111111111111111110000",
"0001111111111111111111111111111111111111111111111111111111111000",
"0000011111111111111111111111111111111111111111111111111111111000",
"0000000111111111111000100111111111111110001010111111111111100000",
"0011000001111111110010001111111111111110100000001111111100000000",
"0011110000011111000110100011111111111111101101100101100000001100",
"0111111100000100011100111001111111111101001000110000000001111110",
"0111111111000001001001101100011111111101101111100100001111111110",
"0111111111111011011100000111001111111000100100001110111111111110",
"0111111111000001000111011100011111111010111110100010010111111110",
"1111111111110111010010010001001111110010010000110111000111111111",
"1111111111100010010110111011101111010111011110011100010111111111",
"1111111111101111110111100001001010000101001011110001110111111111",
"1111111111100000100100111011100010101101101001000100100111111111",
"1111111111110110111101101110001011100000111101011111101111111111",
"1111111111100011100100100011101001110111100101110001000111111111",
"1111111111111000001101110110111011000001001101100100010111111111",
"1111111111111101101000010100001010010101101000110110111111111111",
"1111111111110000111101010101011110110100101110011100011111111111",
"1111111111111010010001110001111000100110000100110001111111111111",
"1111111111111111000111000101101101101100101110100100111111111111",
"1111111111111111110001011111100000111111100010001111111111111111",
"0111111111111111100100001111101011111111111000100111111111111110",
"0111111111111111111111111111111000011111111111111111111111111110",
"0111111111111111111111111111010010111111111111111111111111111110",
"0111111111111111111111111101000111111111111111111111111111111110",
"0011111111111111111111111100010001111111111111111111111111111100",
"0011111110011111111111111111110111111111111111111111111111111100",
"0001111111010111111111111111100011111111111111111111101111111000",
"0001111111000100011111111111001011111111111011111010000111111000",
"0001111111010101001011100101011001010010110001100000101111111000",
"0000111111110001100000100000001100011000000101001110111111110000",
"0000011111110100111101111011100111000011101111101011111111100000",
"0000011111111110100100100010111101110110100000100011111111100000",
"0000001111111100001101101000010001010000111010001111111111000000",
"0000000111111111011000111110110101000101100011111111111110000000",
"0000000111111111001110010100011100010111001000111111111110000000",
"0000000011111111100011110001110110111101111011111111111100000000",
"0000000001111111110110000101000000100001011111111111111000000000",
"0000000000111111111111010111101101101011001111111111110000000000",
"0000000000011111111111110000111100001000011111111111100000000000",
"0000000000000111111111111111111110111111111111111110000000000000",
"0000000000000011111111111111111111111111111111111100000000000000",
"0000000000000000111111111111111111111111111111110000000000000000",
"0000000000000000011111111111111111111111111111100000000000000000",
"0000000000000000000011111111111111111111111100000000000000000000",
"0000000000000000000000111111111111111111110000000000000000000000",
"0000000000000000000000000011111111111100000000000000000000000000"
IT'S SHOWTIME
HEY CHRISTMAS TREE N
YOU SET US UP 1
HEY CHRISTMAS TREE A
YOU SET US UP 1
HEY CHRISTMAS TREE B
YOU SET US UP 1
HEY CHRISTMAS TREE ANS
YOU SET US UP 1
HEY CHRISTMAS TREE I
YOU SET US UP 1
HEY CHRISTMAS TREE FLAG
YOU SET US UP 1

GET YOUR ASS TO MARS N
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY

GET TO THE CHOPPER A
HERE IS MY INVITATION N
HE HAD TO SPLIT 1000
ENOUGH TALK

GET TO THE CHOPPER B
HERE IS MY INVITATION N
I LET HIM GO 1000
ENOUGH TALK

GET TO THE CHOPPER ANS
HERE IS MY INVITATION 1
ENOUGH TALK

GET TO THE CHOPPER I
HERE IS MY INVITATION A
ENOUGH TALK

GET TO THE CHOPPER FLAG
HERE IS MY INVITATION A
GET UP 1
ENOUGH TALK

GET TO THE CHOPPER FLAG
HERE IS MY INVITATION FLAG
HE HAD TO SPLIT 2
ENOUGH TALK

STICK AROUND FLAG
GET TO THE CHOPPER ANS
HERE IS MY INVITATION ANS
YOU'RE FIRED I
ENOUGH TALK
GET TO THE CHOPPER ANS
HERE IS MY INVITATION ANS
I LET HIM GO B
ENOUGH TALK
GET TO THE CHOPPER I
HERE IS MY INVITATION I
GET DOWN 2
ENOUGH TALK
GET TO THE CHOPPER FLAG
HERE IS MY INVITATION FLAG
GET DOWN 1
ENOUGH TALK
CHILL

TALK TO THE HAND ANS

YOU HAVE BEEN TERMINATED
*/
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cmath>
#include<string.h>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<stack>
#include<sstream>
#include<fstream>
#include<time.h>
#include<bitset>
#include<random>
#include<chrono>
#define ZERO 1e-6
#define pi acos(-1)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define gc getchar()
#define fi first
#define se second
#define ls (o<<1)
#define rs (o<<1|1)
#define test printf("!\n");
#define te(x) printf("%s\n",(x));
#define pr(x) write((x),' ');
using namespace std;

/*
typedef __int128_t lll;

struct frac
{
	ll fi,se;
	
	frac():frac(0,1){}
	
	frac(ll a,ll b):fi(a),se(b){}
	
	bool operator < (const frac & b)
	{
		return (LLL)fi*b.se<(LLL)se*b.fi;
	}
	
	bool operator == (const frac & b)
	{
		return (LLL)fi*b.se==(LLL)se*b.fi;
	}
};

ll fac[MAXN];
ll rev[MAXN];
ll re[MAXN];

ll qpow(ll x,ll n,ll mod=MOD)
{
	ll ans=1;
	
	if(n<0)
	{
		return 1;
	}
	while(n)
	{
		if(n&1)
		{
			ans*=x;
			ans%=mod;
		}
		x*=x;
		x%=mod;
		n>>=1;
	}
	
	return ans;
}

ll inv(ll x)
{
	x%=MOD;
	return qpow(x,MOD-2);
}

void mark()
{
	for(int i=0;i<2;i++)
	{
		fac[i]=rev[i]=re[i]=1;
	}
	for(int i=2;i<MAXN;i++)
	{
		fac[i]=(fac[i-1]*i)%MOD;
		rev[i]=(MOD-MOD/i)*rev[MOD%i]%MOD;
		re[i]=re[i-1]*rev[i]%MOD;
	}
}

ll C(ll x,ll y)
{
	if(x<0||x<y)
	{
		return 0;
	}
	return fac[x]*re[y]%MOD*re[x-y]%MOD;
}

bool isprime[MAXN];
int prime[MAXN];
int cnt;

void mark()
{
	memset(isprime,1,sizeof(isprime));
	isprime[0]=isprime[1]=false;
	cnt=0;
	for(int i=2;i<MAXN;i++)
	{
		if(isprime[i])
		{
			prime[cnt++]=i;
		}
		for(int j=0;j<cnt&&i*prime[j]<MAXN;j++)
		{
			isprime[i*prime[j]]=false;
		}
	}
}

struct edge
{
	int to,nxt;
	ll val;
}es[MAXM];

int tot;
int head[MAXN];

void addedge(int u,int v,ll val=1)
{
	es[tot]=edge{v,head[u],val};
	head[u]=tot++;
}

void add(int u,int v,ll val=1)
{
	addedge(u,v,val);
	addedge(v,u,val);
}
*/

typedef unsigned long long ull;
typedef long long ll;
const int MAXN=3e3+10;
const int MAXM=4e6+10;
const ll MOD=998244353;
const ll INF=0x3f3f3f3f;
const ull BASE=233;
const int base=5;
mt19937_64 mt(time(0));

char rubbish[110];
bool GETDATA;
bool PRINT;

inline ll read()
{
	ll x=0,f=1;
	char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-48;ch=getchar();}while(ch>='0'&&ch<='9');
	return x*f;
}

inline void write(ll x,char con='\n')
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10,0);
	putchar(x%10+'0');
	if(con)putchar(con);
}

ll N,M,K,Q;
ll a[MAXN];
ll dp[MAXN][MAXN];

void init()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			dp[i][j]=i==1?0:INF;
		}
	}
}

void solve()
{
	ll ans=0;
	ll cnt;
	
	N=read();
	for(int i=1;i<=N;i++)
	{
		a[i]=read();
	}
	init();
	for(int i=2;i<=N;i++)
	{
		cnt=0;
		for(int j=i-1;j>0;j--)
		{
			if(j+a[j]>=i)
			{
				dp[i][j+a[j]]=min(dp[i][j+a[j]],dp[j][i-1]+cnt);
				cnt++;
			}
		}
		for(int j=i;j<=N;j++)
		{
			dp[i][j]=min(dp[i][j],dp[i][j-1]);
		}
	}
	write(dp[N][N]);
}

int main()
{
	int T;
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	T=1;
	T=read();
	GETDATA=false;
	for(int t=1;t<=T;t++)
	{
		PRINT=false;
		solve();
	}
	
	return 0;
}
/*


*/