该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

许校长为了方便各地的学员参加睿爸暑假集训，开了一家睿爸航空，并承诺，凡是报名了出发地或者目的地睿爸集训的学员及家长，机票半价。

Description

如果城市 $i$ 和 城市 $j$ 间有直达航线，则 $a_{ij}=a_{ji} = 1$ ，否则为 $0$ 。

那么问题来了，能找到多少个三城市组合，两两之间有直达航线。

Format

Input

第一行一个正整数 $N(2<N\le3000)$ ，表示城市数量。

后面一个 $N\times N$ 矩阵，表示任何两个城市之间是否有直达航线。

Output

在一行中输出答案。

Samples

4
1111
1111
1111
1111

4

Limitation

1s, 1024KiB for each test case.