Floyd - existence

The directed weighted graph is given. Using its weighted matrix, determine for each pair of vertices whether there exists a shortest path between them or not.

The shortest path may not exist for two reasons:

• There is no way.

• There is a way of arbitrarily small weight.

Input

The first line contains the number of vertices $n(1\le n\le 100)$. The next $n$ lines contains $n$ numbers that describe the weighted matrix ($j$-th of the $i$-th row corresponds to the weight of the edge from vertex $i$ to vertex $j$). The number $0$ in this matrix represents no edge, and any other number — the existence of an edge of corresponding weight. All the numbers do not exceed $100$ by absolute value.

Output

Print $n$ rows with $n$ numbers: the $j$-th number in the $i$-th row must be $0$ if the path from $i$ to $j$ does not exist, $1$ if there is a shortest path, and $2$ if there is a path of arbitrarily small weight.

Examples