Problem Description

A rock-paper-scissors tournament is held with $ N $ participants. The participants are referred to as participant $ 1 $, participant $ 2 $, $\ldots$, participant $ N $. For any two participants, it is predetermined who will win when they play rock-paper-scissors. This information is represented by positive integers $ A_{i,j} $ ( $1 \leq j < i \leq N$ ), where

• $ A_{i,j} = 0 $ means participant $ i $ loses to participant $ j $,
• $ A_{i,j} = 1 $ means participant $ i $ wins against participant $ j $.

The tournament proceeds as follows:

• Arrange the $ N $ participants in a row in the order of participant $ 1 $, participant $ 2 $, $\ldots$, participant $ N $.
• Randomly select two consecutive participants in the row, have them play a match, and remove the loser from the row. Repeat this process $ N-1 $ times, and the last remaining participant is declared the winner.

Determine the number of participants who have a chance to win the tournament.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_{2,1} $ $ A_{3,1} $ $ A_{3,2} $ $ : $ $ A_{N,1} $ $\ldots$ $ A_{N,N-1} $

Output Format

Output the number of participants who have a chance to win the tournament.

Sample Input and Output

Sample Input #1

3
0
10

Sample Output #1

2

Sample Input #2

6
0
11
111
1111
11001

Sample Output #2

3

Notes/Hints

Constraints

• $1 \leq N \leq 2000$
• $ A_{i,j} $ is either $ 0 $ or $ 1 $

Sample Explanation 1

Participant $ 1 $ wins against participant $ 2 $, participant $ 2 $ wins against participant $ 3 $, and participant $ 3 $ wins against participant $ 1 $. If participants $ 1 $ and $ 2 $ play first, participant $ 3 $ wins the tournament. If participants $ 2 $ and $ 3 $ play first, participant $ 1 $ wins the tournament.

见题面 Input 部分

见题面 Output 部分