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
/*
设F[l][r][0 / 1]表示只考虑区间[l, r]中的人，l / r能否最终活下来
如果x可以获得最终的胜利，那么可以发现1 ~ x和x ~ N中的战斗是独立互不干扰的，所以只要F[1][x][1] = F[x][N][0] = 1即可
考虑转移。以F[l][r][1]为例，即r最后获胜的情况。假设最后一次发生的战斗是x和r之间的，分情况讨论：
(1)x = l。这时候需要有A[r][l] = 1，同时一定存在一个l <= mid <= r - 1，使得F[l][mid][0] = F[mid + 1][r][1] = 1
(2)l + 1 <= x <= r - 1，那么同样可以分成两个过程。这样需要有F[l][x][0] = F[x][r][1] = 1
   （事实上，这是最后一次发生战斗是x和r之间同时合法的必要不充分条件。但是只要满足该条件，F[l][r][1]一定为1，就可以不管了）
这个区间dp可以用压位加速 
*/
#include <bitset>
#include <cstdio>

using namespace std;
const int Max_N(2050);

int N, A[Max_N][Max_N], F[Max_N][Max_N][2];
bitset<Max_N> LG[2][Max_N], RG[2][Max_N];
char input[Max_N];

int main()
{
	scanf("%d", &N);
	for (int i = 2;i <= N;++i)
	{
		scanf("%s", input + 1);
		for (int j = 1;j <= i - 1;++j)
			A[j][i] = 1 - (A[i][j] = input[j] - '0');
	}
	for (int i = 1;i <= N;++i)
		F[i][i][0] = F[i][i][1] = 1, LG[0][i].set(i), LG[1][i].set(i), RG[0][i].set(i), RG[1][i].set(i);
	for (int i = 1;i <= N - 1;++i)
		F[i][i + 1][A[i + 1][i]] = 1, LG[A[i + 1][i]][i].set(i + 1), RG[A[i + 1][i]][i + 1].set(i);
	for (int len = 3;len <= N;++len)
	{
		for (int l = 1, r = len;r <= N;++l, ++r)
		{
			if ((LG[1][l] & RG[1][r]).any())
				F[l][r][1] = 1;
			else
				if (A[r][l] && (LG[0][l] & (RG[1][r] >> 1)).any())
					F[l][r][1] = 1;
			if ((RG[0][r] & LG[0][l]).any())
				F[l][r][0] = 1;
			else
				if (A[l][r] && (RG[1][r] & (LG[0][l] << 1)).any())
					F[l][r][0] = 1;
		}
		for (int l = 1, r = len;r <= N;++l, ++r)
		{
			if (F[l][r][0])
				LG[0][l].set(r), RG[0][r].set(l);
			if (F[l][r][1])
				LG[1][l].set(r), RG[1][r].set(l);
		}
	}
	int Ans(0);
	for (int x = 1;x <= N;++x)
		Ans += (F[1][x][1] & F[x][N][0]);
	printf("%d", Ans);
	return 0;
}