A club of n people (numbered 0 through n-1) records acquaintances in a symmetric n by n matrix of 0s and 1s. The entry in row i, column j is 1 when person i and person j know each other directly, and 0 otherwise. The diagonal entries are always 1 (each person knows themselves). Acquaintance is transitive for grouping: a friend circle is a maximal set of people connected directly or through mutual acquaintances.
Count the number of friend circles.
Input format
Line 1: an integer n.
Next n lines: a string of exactly n characters (each 0 or 1), row i of the matrix. The matrix is symmetric with 1s on the diagonal.
Output format
A single integer: the number of friend circles.
Constraints
- 1 <= n <= 2000
- Row
i, columniis always1; the matrix is symmetric.