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 _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i, a, n) for(LL i = (a), i##_max = (n); i < i##_max; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##min = (a); i >= i##min; --i)
#define ALL(arr) (arr).begin(), (arr).end()
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(NULL); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
template <class T>
T Next() { T buf; cin >> buf; return buf; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "BinaryMatrix.h"
#include "BIT.h"
#include "Factorization.h"
#include "FlowSolver.h"
#include "Graph.h"
#include "LazySegmentTree.h"
#include "Math.h"
#include "Matrix.h"
#include "MinMax.h"
#include "Position.h"
#include "Range.h"
#include "Rational.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "SuffixArray.h"
#include "Tree.h"
#include "UnionFind.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
// template <class T>
// auto Is(const T& value) { return [value](const auto& comparand) -> bool { return comparand == value; }; }
#endif

int N;
bool A[2000][2000];
bitset<2001> L[2000];
bitset<2001> R[2000];
int main() {
	cin >> N;
	REP(i, 0, N) {
		REP(j, 0, i) {
			bool ok = Next<char>() - '0';
			A[i][j] = ok;
			A[j][i] = 1 - ok;
		}
	}

	REP(i, 0, N) {
		L[i][i] = true;
		R[i][i + 1] = true;
 	}

	REP(z, 0, 12) {
		REP(i, 0, N) {
			for (int j = i + 1; j < N; ++j) {
				if (!A[i][j]) continue;
				if ((R[i] & L[j]).any()) {
					R[i] |= R[j];
				}
			}

			for (int j = i - 1; j >= 0; --j) {
				if (!A[i][j]) continue;
				if ((L[i] & R[j]).any()) {
					L[i] |= L[j];
				}
			}
		}
	}

	int cnt = 0;
	REP(i, 0, N) {
		if (L[i][0] && R[i][N]) {
			++cnt;
		}
	}
	cout << cnt << endl;
	return 0;
}
