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 <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <bitset>
#include <utility>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;

using bits = bitset<2001>;
// using bits = bitset<10>;

// vector<vector<bits>> dp;
// vector<vector<int>> calc;
// bits& rec(vector<bits>& a, int l, int r){
//   if(calc[l][r]) return dp[l][r];
//   if(r-l == 0){
//     dp[l][r].set(l, 1);
//     calc[l][r] = 1;
//     return dp[l][r];
//   }
//   if(r-l == 1){
//     dp[l][r].set(l, 1);
//     calc[l][r] = 1;
//     return dp[l][r];
//   }
//   if(r-l == 2){
//     if(a[l][l+1]){
//       dp[l][r].set(l, 1);
//     }else{
//       dp[l][r].set(l+1, 1);
//     }
//     calc[l][r] = 1;
//     return dp[l][r];
//   }
//   for(int i=l; i<r; i++){
//     bool bl = true;
//     bool br = true;
//     if(i > l){
//       if((rec(a, l, i) & a[i]).count() == 0){
//         bl = false;
//       }
//     }
//     if(i+1 < r){
//       if((rec(a, i+1, r) & a[i]).count() == 0){
//         br = false;
//       }
//     }
//     if(bl && br){
//       dp[l][r].set(i, 1);
//     }
//   }
//   calc[l][r] = 1;
//   return dp[l][r];
// }

int main(){
  int n;
  cin >> n;

  vector<bits> a(n);
  vector<vector<int>> b(n, vector<int>(n));
  for(int i=1, j=1; i<n; i++, j++){
    string s;
    cin >> s;

    for(int k=0; k<j; k++){
      b[i][k] = s[k] == '1' ? 1 : 0;
      b[k][i] = !b[i][k];
    }
  }

  for(int i=0; i<n; i++){
    // a[i].set(i);
    for(int j=0; j<n; j++){
      if(b[i][j]){
        a[i].set(j);
      }
    }
  }

  // dp = vector<vector<bits>>(n+1, vector<bits>(n+1));
  // calc = vector<vector<int>>(n+1, vector<int>(n+1));

  // auto& v = rec(a, 0, n);
  // int ans = v.count();
  // println(ans);

  vector<bits> dpl(n+1), dpr(n+1);
  for(int i=0; i<n; i++){
    dpl[i].set(i);
    dpr[i].set(i);
  }

  for(int len=2; len<=n; len++){
    // vector<pair<int,int>> nwl, nwr;
    for(int l=0; l+len<=n; l++){
      int r = l+len-1;
      if((dpl[l+1] & dpr[l+len-1] & a[l]).count()){
        dpr[l+len-1].set(l, 1);
        // nwr.emplace_back(l+len-1, l);
      }
      if((dpr[r-1] & dpl[l] & a[r]).count()){
        dpl[l].set(r, 1);
        // nwl.emplace_back(l, r);
      }
    }
    // for(auto p: nwl){
    //   dpl[p.first].set(p.second);
    // }
    // for(auto p: nwr){
    //   dpr[p.first].set(p.second);
    // }
  }

  int ans = (dpl[0] & dpr[n-1]).count();
  println(ans);

  // for(int i=0; i<n; i++){
  //   eprint(dpl[0][i]);
  // }
  // eprintln("");

  // for(int i=0; i<n; i++){
  //   eprint(dpr[n-1][i]);
  // }
  // eprintln("");
  return 0;
}
