We will host a rock-paper-scissors tournament with N people. The participants are called Person 1, Person 2, \ldots, Person N. For any two participants, the result of the match between them is determined in advance. This information is represented by positive integers A_{i,j} ( 1 \leq j < i \leq N ) as follows:

* If A_{i,j} = 0, Person j defeats Person i.
* If A_{i,j} = 1, Person i defeats Person j.



The tournament proceeds as follows:

* We will arrange the N participants in a row, in the order Person 1, Person 2, \ldots, Person N from left to right.
* We will randomly choose two consecutive persons in the row. They will play a match against each other, and we will remove the loser from the row. We will repeat this process N-1 times, and the last person remaining will be declared the champion.



Find the number of persons with the possibility of becoming the champion.

Constraints

* 1 \leq N \leq 2000
* A_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:


N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}


Output

Print the number of persons with the possibility of becoming the champion.

Examples

Input

3
0
10


Output

2


Input

6
0
11
111
1111
11001


Output

3
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 1000003
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}
 
 
long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if ((j & 1LL)){
				res *= i;
				if (res >= MOD){
					res %= MOD;
				}
			}
			j >>= 1;
			i *= i;
			if (i >= MOD){
				i %= MOD;
			}
		}
		return res;
	}
class Combination{
	
public:
	vector<long long int> k;
	vector<long long int> r;
	void resize(int N){
		k.resize(N + 2);
		r.resize(N + 2);
		k[0] = 1;
		for (int i = 1; i < N+2; i++){
			k[i] = k[i - 1];
			k[i] *= i;
			if (k[i] >= MOD)k[i] %= MOD;
		}
		long long int al = k[k.size() - 1];
		long long int iv = ppow(k[k.size() - 1],MOD-2);
		r[k.size() - 1] = iv;
		for (int i = (int)(r.size()) - 2; i >= 0; i--){
			r[i] = r[i + 1] * (i + 1);
			if (r[i] >= MOD){
				r[i] %= MOD;
			}
		}
	}
	long long int C(int a, int b){
		if (a < b)return 0;
		long long int up = k[a];
		long long int dw = r[b] * r[a - b];
		dw %= MOD;
		up *= dw;
		up %= MOD;
		return up;
	}
	long long int H(int a, int b){
		return C(a + b - 1, b);
	}
	long long int catalan_number(int n){
		return (C(2 * n, n) + MOD - C(2 * n, n - 1)) % MOD;
	}
};
Combination C;



long long int extgcd(long long int a,long long int b,long long int &x,long long int &y){
	long long int d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	else{
		x=1;
		y=0;
	}
	return d;
}
long long int modinverse(long long int a,long long int b){   //aの逆元を求める(mod b)
	long long int x,y;
	long long int d=extgcd(a,b,x,y);
	return (x%b+b)%b;
}

#define MAX 2002
int n;

bitset<MAX> dpl[MAX];
bitset<MAX> dpr[MAX];

bitset<MAX> win[MAX];

char buf[MAX];

int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		scanf("%s",buf);
		for(int j=0;j<i;j++){
			int a=buf[j]-'0';
			if(a==1){
				win[i].set(j,1);
			}
			else{
				win[j].set(i,1);
				//cerr<<j<<" "<<i<<endl;
			}
		}
	}
	for(int i=0;i<n;i++){
		dpl[i].set(i,1);
		dpr[i].set(i,1);
	}
	for(int interval=1;interval<n;interval++){
		for(int lef=0;lef+interval<n;lef++){
			int rig=lef+interval;
			if((dpl[rig]&dpr[lef+1]&win[lef]).any()){
				dpl[rig].set(lef,1);
				//cerr<<"OK"<<" "<<lef<<" "<<rig<<endl;
			}
		}
		for(int rig=n-1;rig-interval>=0;rig--){
			int lef=rig-interval;
			if((dpl[rig-1]&dpr[lef]&win[rig]).any()){
				dpr[lef].set(rig,1);
				//cerr<<"ok2"<<endl;
			}
		}
	}
	cout<<(dpl[n-1]&dpr[0]).count()<<endl;
	return 0;
}
