Migrated from Lutece 1287 MC挖矿世界

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

银牌爷和柱神开始玩 MC 啦，但是怪物实在是太多了，于是银牌爷决定去挖点钻石提升装备。

来到矿脉的银牌爷发现矿脉错综复杂。

矿脉是由一些矿洞和一些通道组成的，通道连着不同的矿洞。矿洞的编号从 $1$ 到 $n$。

聪明的银牌爷定义了矿脉的复杂度为下面的式子：

其中 $\delta(i,j)$ 表示矿洞 $i$ 到矿洞 $j$ 的最短路。如果最短路不存在，则为 $n$。

现在给出一个矿脉，银牌爷想知道这个矿脉的复杂度是多少？

Input

输入一个整数 $n$（$1\le n\le 2000$），表示总共 $n$ 个矿洞。

接下来 $n$ 行 $n$ 列，第 $i$ 行 $j$ 列的值 $a_{ij}=1$ 或者 $a_{ij}=0$，如果 $a_{ij}=1$，表示从矿洞 $i$ 到矿洞 $j$ 有一条长为 $1$ 的边，如果 $a_{ij}=0$，则表示从 $i$ 到 $j$ 没有直接的边。

Output

输出一个整数，表示矿脉的复杂度。

Samples

3
010
001
100

15

2
10
01

8

Resources

咦。。。