题目描述

小 N 家的花园可以被看做一个 $n\times n$ 的网格图，从上到下依次为第 $1$ 行至第 $n$ 行，从左到右分别为第 $1$ 列至第 $n$ 列。

现在小 N 要在花园的某些位置种上花，具体来说，可以用 $c_{i,j}$ 来表示花园的第 $i$ 行第 $j$ 列处是否种有花，$c_{i,j}=0$ 表示这个位置没有种花，$c_{i,j}=1$ 则表示这个位置种有一朵花。

小 N 希望她的花园中每个位置都种有花。换言之，她希望对任意的 $1\le i,j\le n$，均有 $c_{i,j}=1$。

为了达成这一目的，小 N 找来了魔法师小 L。小 L 可以使用魔法将花园中某一行的所有花朵和空地原封不动地复制到某一列上，这可能使某些位置凭空生成一朵花，也可能使某些原本种有一朵花的位置变为空地。

具体来说，小 L 在施法时会先选择 $i,j$ 满足 $1\le i\le n,1\le j\le n$，接下来对每个 $1\le k\le n$ 设 $p_k=c_{i,k}$，最后对每个 $1\le l\le n$，$c_{l,j}$ 的值会变为 $p_l$。

为了节省魔力，小 L 希望最小化施法的次数。请你帮小 L 求出至少需要多少次施法才能达成小 N 的心愿，即对每个 $1\le i,j\le n$，均有 $c_{i,j}=1$。保证存在一种可行的施法方案。

输入格式

第一行一个正整数 $n$ 表示花园的大小。

接下来 $n$ 行每行有 $n$ 个数，第 $i+1$ 行第 $j$ 列的数表示 $c_{i,j}$ 的值。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

2
01
10

样例输出 #1

3

提示

小 L 进行三次施法即可将每个位置都种上花。下面是一种可行的施法过程。

第一次施法时，选择 $i=1,j=2$，此时 $c$ 变为

00
11

第二次施法时，选择 $i=2,j=1$，此时 $c$ 变为

10
11

第三次施法时，选择 $i=2,j=2$，此时 $c$ 变为

11
11

此时对每个 $1\le i,j\le n$ 均有 $c_{i,j}=1$，即花园中的每个位置都被种上了一朵花。可以证明不存在次数更少的施法方案。

[点我下载大样例](file://fountain.zip)

【测试点约束】

对于所有数据，$1\le n\le 3000$。

• 特殊性质 A：存在 $1\le i\le n$，使得对任意 $1\le j\le n$，均有 $c_{i,j}=1$。