Linear Algebra and Applications

To celebrate taking a linear algebra course, Cheongung gives Hyowon an $n\times n$ matrix $A$ as a gift. To make it easy to work with, every entry is a nonnegative integer, and the matrix has at most $5n$ nonzero entries. In the spirit of taking linear algebra, Hyowon computes $A^2$ and finds that $A+A^2$ has no more zero entries than $A$. Likewise, $A+A^2+A^3$ has no more zero entries than $A+A^2$. Hyowon falls into this train of thought.

"Could there be some $k$ for which $A+A^2+\cdots+A^k$ has no zero entries at all? If such a $k$ exists, what is the smallest one?"

Hyowon asks Cheongung about this and receives the answer "If $k$ exists, then by the Cayley-Hamilton theorem it is at most $n$..." For Hyowon, who is not satisfied with this answer, write a program that determines whether such a $k$ exists and, if it does, prints its smallest value.

The first line gives the size of the matrix, $n$, where $5\leq n\leq 1,000$.

The $n\times n$ matrix $A$ is given over the second line through the $(n+1)$-th line. Each line contains $n$ integers separated by spaces, and the $j$-th number on the $(i+1)$-th line is $a_{ij}$. Each entry satisfies $0\leq a_{ij}\leq 10^9$, and at most $5n$ of the $a_{ij}$ are greater than $0$.

If a $k$ satisfying the condition exists, print the smallest such $k$. If no such $k$ exists, print 0.