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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000003;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	int n,i,j,k;cin>>n;
	vector<bitset<2000>>towin(n);
	for(i=1;i<n;i++){
		string str;cin>>str;
		for(j=0;j<i;j++){
			if(str[j]=='1'){towin[i][j]=1;}
			else{towin[j][i]=1;}
		}
	}
	vector<bitset<2001>>Lwin(n);//どこまで勝てるか 自分より小さい側
	vector<bitset<2001>>Rwin(n);//どこまで勝てるか 自分より大きい側
	for(i=0;i<n;i++){
		Lwin[i][i]=1;
		Rwin[i][i+1]=1;
		bitset<2001>cha;
		for(j=i-1;j>=0;j--){
			if(towin[i][j]&&((Lwin[i]&Rwin[j]).any()))
				{Lwin[i]|=Lwin[j];}
			if(((cha&Rwin[j]).any())||(towin[j][i]&&((Lwin[i]&Rwin[j]).any())))
				{Rwin[j][i+1]=1;cha[j+1]=1;}
		}
	}
	int ans=0;
	for(i=0;i<n;i++){
		/*for(j=0;j<=n;j++){
			if(Lwin[i][j]||Rwin[i][j]){cerr<<'1';}
			else{cerr<<'0';}
		}
		cerr<<endl;*/
		if(Lwin[i][0]&&Rwin[i][n]){ans++;}
	}
	cout<<ans<<endl;
	return 0;
}
