다양한 티셔츠

혁신적인 의상 패턴 대회(ICPC)가 다가오고 있다. 주최 측은 참가자들의 티셔츠가 다양성과 스타일 면에서 높은 기준을 충족하기를 원한다.

주최 측은 서로 다른 $N$개의 모델을 제공하는 티셔츠 업체와 협상 중이다. 각 모델은 글자 색과 배경 색의 고유한 조합으로 정의되며, 1부터 $N$까지의 정수가 번호로 부여된다.

선택한 티셔츠가 시각적으로 다양하도록, 선택된 두 모델은 같은 글자 색이나 같은 배경 색을 가질 수 없다. 예를 들어 파란 배경에 빨간 글씨인 모델과 흰 배경에 빨간 글씨인 모델은 둘 중 하나만 고를 수 있다. 검은 배경에 흰 글씨인 모델과 흰 배경에 검은 글씨인 모델은 색이 겹치지 않으므로 둘 다 고를 수 있다.

업체는 함께 선택할 수 없는 모든 모델 쌍을 표시한 $N \times N$ 이진 행렬 $A$를 제공한다. $i \ne j$이고 모델 $i$와 $j$가 글자 색이나 배경 색을 공유하여 함께 고를 수 없으면 $A_{i,j} = 1$이다. 그렇지 않으면 $A_{i,j} = 0$이다.

다양성 규칙을 지키면서 고를 수 있는 모델의 최대 개수를 구하라.

첫 번째 줄에 티셔츠 모델의 개수를 나타내는 정수 $N$ ($1 \le N \le 1000$)이 주어진다.

이어지는 $N$개의 줄에는 길이가 $N$인 이진 문자열이 한 줄씩 주어진다. $i$번째 문자열의 $j$번째 문자는 $A_{i,j}$의 값이다.

입력 행렬과 일치하는 모델 집합이 적어도 하나 존재함이 보장된다.

다양성 규칙을 어기지 않고 고를 수 있는 티셔츠 모델의 최대 개수를 한 줄에 정수로 출력한다.