Is there a cycle?

Input

The first line contains a single integer — the number of vertices n~(n \le 50).

Then follow $n$ lines, each containing $n$ integers — the adjacency matrix of the graph. Each number is either $0$ or $1$. The $j$-th number in the $i$-th line is equal to $1$ if and only if there is an edge from vertex $i$ to vertex $j$.

It is guaranteed that the main diagonal of the matrix contains only zeros.

Output

Print $0$ if the graph contains no cycles, and $1$ if there is at least one cycle.

Examples