Oriented graph is given. Determine, does it contain a cycle.

Input

First line contains number of vertices n (n ≤ 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.