Hay \(N\) modelos de polera; cada modelo es una combinación distinta de un color de letra y un color de fondo. Se quiere elegir la mayor cantidad posible de modelos de modo que no haya dos elegidos con el mismo color de letra ni con el mismo color de fondo.

No se conocen los colores: solo se tiene la matriz \(A\) de \(N \times N\) donde \(A_{i,j} = 1\) si \(i \ne j\) y los modelos \(i\) y \(j\) comparten el color de letra o el de fondo, y \(A_{i,j} = 0\) en otro caso. Calcula el máximo de modelos que se pueden elegir.

Entrada

La primera línea tiene un entero \(N\) \((1 \le N \le 1000)\).

Cada una de las siguientes \(N\) líneas tiene un texto binario de largo \(N\): el \(j\)-ésimo carácter de la \(i\)-ésima línea es \(A_{i,j}\).

Se garantiza que existe al menos una asignación de colores que produce esa matriz.

Salida

Una línea con la máxima cantidad de modelos que se pueden elegir.

Ejemplo 1

Entrada

3
011
101
110

Salida

1

Ejemplo 2

Entrada

3
010
101
010

Salida

2

Regional Latinoamericana 2024 del ICPC, problema D («Diverse T-Shirts»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.