Bobo 有一个无向图，其 $n$ 个顶点被方便地标记为 $1, 2, \dots, n$。设 $V$ 为顶点集，$E$ 为边集。他想要计算满足以下条件的元组 $(v_1, v_2, \dots, v_6)$ 的数量：

• $v_1, v_2, \dots, v_6 \in V$；
• $\{v_1, v_2\}, \{v_2, v_3\}, \dots, \{v_5, v_6\}, \{v_6, v_1\} \in E$；
• $C = (\{v_1, v_2\}, \{v_2, v_3\}, \dots, \{v_5, v_6\}, \{v_6, v_1\})$ 不是一个长度为 6 的简单环。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 1000$)。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的字符串 $g_i$，其中 $g_{i,j}$ 表示边 $\{i, j\}$ 的存在性（$g_{i,j} \in \{0, 1\}$，$g_{i,i} = 0$，$g_{i,j} = g_{j,i}$）。

保证所有测试用例的 $n$ 之和不超过 1000。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的元组数量。

样例

样例输入 1

3
011
101
110
4
0101
1010
0101
1010
6
011111
101111
110111
111011
111101
111110

样例输出 1

66
128
14910