Fast Fingers Thomas has just finished conducting a tryout for a poutine-eating contest, and needs to produce a ranklist. However, the scoreboard has crashed and the rankings are lost! Individual $i$ beat individual $j$ if individual $i$ ate more poutine than individual $j$. He vaguely remembers that some individuals ate more poutine than other individuals, but might not have enough data to fully reconstruct the ranklist. He does remember that there were no ties in the contest.

He decides to email all the participants with a list of pairs of individuals, and expects to get a response with, for each pair, which individual did better.

Compute the minimum possible size of the list such that, independent of what responses he gets back with regards to which individual ate more poutine, he is guaranteed to be able to construct a correct full ranklist.

Constraints

$1\le N\le 500$

There exists some ranklist consistent with the input.

Input Specification

The first line contains a single positive integer, $N$.

The next $N$ lines contain a binary string of length $N$. If the $j$th character of the $i$th line is 1, then individual $i$ definitely did better than individual $j$. Otherwise, the $j$th character of the $i$th line is 0.

Output Specification

Output the minimum number of pairs needed to always ascertain the ranklist.

Sample Input

3
011
000
000

Sample Output

1