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

/*

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_f

人Xが優勝する可能性があるかをO(N)で求めればいい
人0を優勝させるためには、まず0が勝てない人を全員排除する必要がある
→stackとかで解けないかな…？

勝ち方向をグラフで表したとき、そこからすべて到達可能ならば優勝可能…？
→違いそうだし計算量的に不可能

右端から、この区間で勝つ可能性がある人のリストを構築していく
ある人が勝つ可能性がある条件は、それより右にいる優勝者候補の中に勝てる人がいること？
十分条件ではあるけど…
→逆に優勝者候補全てに勝てないとする
→優勝者候補以外ですべての優勝者を倒せる

今までの優勝者候補が優勝者であり続ける or 新たなる優勝者候補が生まれる条件は？
新規追加の人に誰も勝てなければ全員優勝者候補ではなくなる

優勝者候補の人は、直接勝てれば候補のまま
直接勝てない場合・・・面倒くさい
優勝候補じゃない場合、
→この考え方は無理がありそう

=====解説を見た=====
bitsetかぁ…
つまりO(N^3)解を見つければいい

さっき考えてたのがO(N^3)か
dpL[j][i] = i…jを考えたとき、iが優勝する可能性がある
dpR[i][j] = i…jを考えたとき、jが優勝する可能性がある

答えは ΣdpL[N-1][i]&dpR[0][i]
dpL[j][i] = Σ(or)A[i][x] & dpR[i+1][x] & dpL[j][x]
dpR[i][j] = Σ(or)A[j][x] & dpR[i][x] & dpL[j-1][x]

かぶらないためには、j-iが小さいほうから計算していく

*/

#include <bits/stdc++.h>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <bitset>

using namespace std;

#define rep(i,n,m) for(ll (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)
using ll = int;
const ll mod = 998244353;


int main(){

    int N;
    int tmp;
    char tmpc = '\n';
    bitset<2000> tmpset;

    scanf ("%d",&N);
    vector<bitset<2000>> A(N);
    rep(i,2,N+1){
        rep(j,1,i){
            while (tmpc == '\n'){
                scanf ("%c",&tmpc);
            }
            tmp = tmpc-'0';
            tmpc = '\n';

            A[i-1][j-1] = (bool)tmp;
            A[j-1][i-1] = (bool)(tmp^1);
        }
    }

    //cout << A[0] << endl;
    vector<bitset<2000>> dpL(N);
    vector<bitset<2000>> dpR(N);

    rep(j_i,0,N){
        rep(i,0,N-j_i){
            int j = i+j_i;

            if (i == j){
                dpL[j][i] = true;
                dpR[i][j] = true;
            }else{
                tmpset = A[i] & dpR[i+1] & dpL[j];
                bool lans = tmpset.any();
                tmpset = A[j] & dpR[i] & dpL[j-1];
                bool rans = tmpset.any();
                dpL[j][i] = lans;
                dpR[i][j] = rans;
            }
        }
    }

    tmpset = dpL[N-1]&dpR[0];
    cout << tmpset.count() << endl;

}