问题描述

给定一个由 $0$ 和 $1$ 构成的 $n\times n$ 矩阵 $A_{i,j}$，你需要求出矩阵中岛屿的数量。

岛屿：如果两个格子相邻（上下左右）且这两个格子均为 $1$，则这两个格子为同一个岛屿。

输入格式

第一行输入一个整数 $n$。$(1\le n\le 500)$。

接下来 $n$ 行，每行输入 $n$ 个整数（$0$ 或 $1$）。

输出格式

输出 $1$ 个整数，表示岛屿的数量。

样例输入

3
1 0 1
1 0 0
0 1 0

样例输出

3