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
#define y1 askjdkasldjlkasd
#include <bits/stdc++.h>
#undef y1

using namespace std;

#define pb push_back
#define mp make_pair
#define fi(a, b) for(int i=a; i<=b; i++)
#define fj(a, b) for(int j=a; j<=b; j++)
#define fo(a, b) for(int o=a; o<=b; o++)
#define fdi(a, b) for(int i=a; i>=b; i--)
#define fdj(a, b) for(int j=a; j>=b; j--)
#define fdo(a, b) for(int o=a; o>=b; o--)
#define sz(x) (int)x.size()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while (0)
#endif

double START_TIME;

void exit() {
#ifdef LOCAL	
	cerr << "TIME: " << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;
#endif	
	exit(0);
}

template<typename A, typename B>
ostream& operator<<(ostream& os, pair<A, B> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T> v) {
	fi(0, sz(v) - 1) {
		os << v[i] << " ";
	}
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T> t) {
	for (auto z : t) {
		os << z << " ";
	}
	return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, map<T1, T2> t) {
	cerr << endl;
	for (auto z : t) {
		os << "\t" << z.first << " -> " << z.second << endl;
	}
	return os;
}

#ifdef LOCAL
#define dbg(x) {cerr << __LINE__ << "\t" << #x << ": " << x << endl;}
#define dbg0(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 0; ABC < n; ABC++) cerr << x[ABC] << ' '; cerr << endl;}
#else
#define dbg(x) while(0){}
#define dbg0(x, n) while(0){}
#endif

#ifdef LOCAL
#define ass(x) if (!(x)) { cerr << __LINE__ << "\tassertion failed: " << #x << endl, abort(); }
#else
#define ass(x) assert(x)
#endif

///////////////////////////////////////////////////

const int MAX = 2e3 + 41;
//const int MAX = 10;

int n;
bitset<MAX> pref[MAX], suf[MAX], win[MAX], can[MAX];
int a[MAX][MAX];

void solve () {
	fi(0, n - 1) {
		fj(0, n - 1) {
			if (a[i][j]) win[i].set(j);
		}
	}
//	fi(0, n - 1) dbg(win[i]);
//	dbg(win[0]);
	fi(0, n - 1) {
		pref[i].set(i);
		suf[i].set(i);
		can[i].set(i);
		fdj(i - 1, 0) {
			if (a[i][j]) {				
				if ( ( (suf[j] << 1) & pref[i]).count() ) {
					pref[i] |= pref[j];
				}
			}
		}
		fdj(i - 1, 0) {
			if ( (pref[i] & (suf[j] << 1)).count() ) {
				can[j].set(i);
			}
		}
		bitset<MAX> sufwin;
		sufwin.reset();
		sufwin.set(i);
		fdj(i - 1, 0) {
			if ( (sufwin & win[j] & can[j]).count() ) {
				sufwin.set(j);
				suf[j].set(i);
			}
		}
/*
		fj(0, i) {
			dbg(pref[j]);
			dbg(suf[j]);
		}
		err("after i = %d\n", i);
*/
	}
	vi answer;
	fi(0, n - 1) {
		if (pref[i].test(0) && suf[i].test(n - 1)) {
			answer.pb(i);
		}
	}
	printf("%d\n", sz(answer));
//	dbg(answer);	
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	START_TIME = (double)clock();
#endif
	
	scanf("%d", &n);
	fi(1, n - 1) {
		char str[MAX];
		scanf("%s", str);		
		fj(0, i - 1) {			
			a[i][j] = str[j] - '0';
			a[j][i] = 1 - a[i][j];
		}
	}
	solve();

	exit();
	return 0;
}



