Bobo 有一个有向图 $G$，其顶点编号为 $1, 2, \dots, n$。令 $\delta(i, j)$ 为从顶点 $i$ 到顶点 $j$ 的最短路径上的边数（如果最短路径不存在，则 $\delta(i, j) = n$）。 Bobo 想要计算 $\sum_{i=1}^n \sum_{j=1}^n \delta^2(i, j)$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2000$)。 接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $g_{i,1}, g_{i,2}, \dots, g_{i,n}$ ($0 \le g_{i,j} \le 1$)。如果存在从顶点 $i$ 到顶点 $j$ 的边，则 $g_{i,j} = 1$。否则，$g_{i,j} = 0$。

输出格式

输出一个整数，表示 $\sum_{i=1}^n \sum_{j=1}^n \delta^2(i, j)$。

样例

输入 1

3
010
001
100

输出 1

15

输入 2

2
10
01

输出 2

8