Description

我们的郭嘉大大在曹操这里过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（<=1000）个袁绍的侦探，将他们从1到N进行编号，同时他们之间存在一种传递关系，即若C[i,j]=1,则侦探i能将消息直接传递给侦探j。
现在，曹操要发布一个消息，需要传达给所有侦探，而我们的郭嘉大大则需要传递给尽量少的侦探使所有的侦探都知道这一个消息，问我们至少要传递给几个侦探？

Format

Input

第一行为 N；
第二行至第N+1行为N×N的矩阵（若第i行第j列为1，则侦探i能将消息直接传递给侦探j，若第i行第j列为0，则侦探i不能将消息直接传递个侦探j）。

Output

输出只有一行：即我们的郭嘉大大首先至少要传递的侦探个数。

Sample 1

Input

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

Output

2

Limitation

1s, 64MiB for each test case.