Binary Matrix

Time limit0.5sMemory limit512 MB

Summary

Given an n by n binary matrix K, find the smallest k such that K^k equals K^m for some earlier m, computing entries mod 2.

Level: Medium5 of 10
Topics: Matrix, Math, Simulation
Solved: No attempts yet

Problem

Kipa received an n by n table filled with 0 and 1 as a gift from Yul. Kipa treats the table as a matrix and names it $K$ . Kipa likes that every entry of $K$ is either 0 or 1, so Kipa decides to write 0 for an even value and 1 for an odd value in every entry of each computed result.

Kipa first tried adding, computing $K$ , $K+K$ , and $K+K+K$ , but soon lost interest because $K+K$ is all zeros. So Kipa turned to multiplication. While computing $K$ , $K^2$ , $K^3$ , and so on, Kipa noticed the same computation seemed to repeat.

Kipa thinks a computer should do repetitive work, so Kipa wants to know when the multiplication becomes boring. Write a program that prints how many times $K$ appears in the product expression when Kipa sees a previous result again.

Input

The first line contains the size $n$ of the matrix.

The next $n$ lines contain $n$ numbers in total, separated by spaces. Every number is either 0 or 1.

Output

Print the number of times $K$ appears in the product expression when Kipa sees a previous result again.

Hint

Stated mathematically, given a matrix $K$ , print the smallest element of the subset of natural numbers

$\{n : \exists m, 1 \le m < n \text{ and } K^m = K^n\}$

Examples2

Example 1
Input
```
4
0 1 1 1
1 0 1 1
0 0 0 1
0 1 0 0
```
Expected output
```
5
```

Example 2

Input

16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0
0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0
0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0
0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0
0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0
0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0
0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0
0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

Expected output