题目描述

有 $n$ 个地点，地点之间存在一些有向路径。如果从地点 $i$ 可以沿若干条有向路径最终回到 $i$，那么称地点 $i$ 是满足要求的。

你可以在任意两个地点之间新增有向路径，也允许新增从某个地点指向它自身的路径。

请计算至少需要新增多少条有向路径，才能使所有地点都满足要求。换句话说，最终每个地点都必须位于至少一个有向环上，其中自环也算作有向环。

输入格式

第一行输入一个整数 $n$，表示地点数量。

接下来输入 $n$ 行，每行一个长度为 $n$ 的 01 字符串。第 $i$ 行第 $j$ 个字符表示是否存在从地点 $i$ 到地点 $j$ 的直接路径：

• 1：存在；
• 0：不存在。

地点编号为 $0,1,\ldots,n-1$。

输出格式

输出一个整数，表示最少需要新增的有向路径数量。

样例 1

输入

3
010
100
000

输出

1

样例 2

输入

4
0110
0001
0101
1000

输出

0

样例 3

输入

5
00101
00010
00010
10000
00000

输出

1

样例解释

样例 1 中，地点 $0$ 与地点 $1$ 已经位于一个有向环中，而地点 $2$ 不在任何有向环中。只需增加一条 $2\to2$ 的自环即可。

样例 2 中所有地点原本就都能够沿有向路径回到自身，因此答案为 $0$。

数据范围

• $2\le n\le20$；
• 邻接矩阵中只包含字符 0 和 1；
• 允许原图中存在自环。