선형대수학과 응용

선형대수학을 수강하는 기념으로 청응이가 효원이에게 $n\times n$ 행렬 $A$를 선물해줬다. 계산하기 편하라고 모든 항이 음이 아닌 정수이고 0이 아닌 항이 $5n$개 이하인 행렬을 줬다. 선형대수학을 수강하는 기대 속에 효원이는 $A^2$을 계산해봤고, $A+A^2$은 $A$보다 0인 항의 개수가 작거나 같다는 것을 확인했다. 마찬가지로 $A+A^2+A^3$은 $A+A^2$보다 0인 항의 개수가 작거나 같았다. 효원이는 이런 고민에 빠지게 되었다.

"어떤 $k$가 존재해서 $A+A^2+\cdots+A^k$은 0인 항이 아예 없을 수도 있을까? 그런 $k$가 존재한다면 최솟값은 얼마일까?"

효원이가 청응이에게 이걸 물어봤더니 "$k$가 존재한다면 Cayley-Hamilton 정리에 따라 $n$보다 작거나 같을 건데..."라는 대답을 받았다. 이 답변에 만족하지 않은 효원이를 위해, $k$가 존재하는지, 존재한다면 최솟값을 출력하는 프로그램을 작성하시오.

첫 줄에는 행렬의 크기 $n$이 주어지며, $5\leq n\leq 1,000$을 만족한다.

둘째 줄부터 $(n+1)$번째 줄에 걸쳐 $n\times n$ 행렬 $A$가 주어진다. 각 줄에는 $n$개의 정수가 공백으로 구분되어 주어지며, $(i+1)$번째 줄의 $j$번째 수가 $a_{ij}$에 해당한다. 각 항은 $0\leq a_{ij}\leq 10^9$을 만족하며, $a_{ij}$ 중 $0$보다 큰 항이 $5n$개 이하이다.

조건을 만족하는 $k$가 존재한다면 최소 $k$를 출력하시오. 조건을 만족하는 $k$가 없다면 0을 출력하시오.