Is there a cycle?

The directed graph is given. Determine, does it contain a cycle.

Input

First line contains number of vertices $n(n\le 50)$. Each of the next $n$ lines contains $n$ numbers, each of them is either $0$ or $1$. $j$-th number in the $i$-th line equals to $1$ if and only if there exist an edge from $i$-th vertex to $j$-th. It is guaranteed that diagonal of the matrix contains zeros.

Output

Print $0$ if there is no cycle in the graph and $1$ if cycle exists.

Examples