Newcomer and Veteran

Jongwoo organizes the SPC (Saenaegi Programming Contest). As the name suggests, the SPC is a contest open only to newcomers. Jongwoo suspects that veterans may have slipped in among the SPC participants. So he decided to collect reports of veterans, asking each participant to name the veterans they know of.

Not every report can be taken at face value, however. It is not yet known whether the person who filed a report is a newcomer or a veteran. A report from a newcomer would be fine, but a veteran could pretend to be a newcomer and report someone else. In that case the report becomes hard to believe. Thinking it over, Jongwoo realized the following rules hold.

1. Every participant is either a newcomer or a veteran.
2. If a participant is a newcomer, every report that person filed is true.
3. If a participant is a veteran, every report that person filed is false.

A report being true means the person reported is indeed a veteran, and a report being false means the person reported is a newcomer. Jongwoo now wants to prepare for the worst case, that is, the case with the most veterans. Given the current reports, what is the largest number of veterans possible among all configurations consistent with the rules? Let us compute it.

The first line gives an integer N (1 ≤ N ≤ 2,000), the number of participants.

The next N lines give the current report situation as N characters each. If the y-th character of the x-th line is 1, participant x reported participant y; if it is 0, participant x did not report participant y.

The input never contradicts the rules given in the statement.

Print the largest possible number of veterans in the current report situation under the rules in the statement.