矩阵的周期

Problem Description

给定一个 $n\times n$ 的01矩阵 $\textbf{M}$，令 $f ( i , j , k ) = [(\textbf{M}^k)_{i,j}\neq 0]$，请对于每对 $(i,j)$ ($1\leq i,j\leq n$)，找出最小的正整数 $t$，满足当 $k$ 充分大时必有 $f ( i , j , k ) = f ( i , j , k + t )$。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 20$)，表示测试数据的组数。 每组数据第一行包含一个正整数 $n$ ($1\leq n\leq 60$)，表示矩阵的大小。 接下来 $n$ 行，每行一个长度为 $n$ 的01串，第 $i$ 行第 $j$ 列表示 $\textbf{M}_{i,j}$ ($1\leq i,j\leq n$)。

Output

对于每组数据输出 $n$ 行，第 $i$ ($1\leq i\leq n$) 行输出 $n$ 个整数，其中第 $j$ ($1\leq j\leq n$) 个整数表示最小的正整数 $t$，满足当 $k$ 充分大时必有 $f( i , j , k ) = f ( i , j , k + t )$；若找不到这样的 $t$，输出 ''$\texttt{-1}$''。

Sample Input

1
9
010010000
001000001
000100000
010000000
000001000
000000100
000000010
000010001
000000000

Sample Output

1 3 3 3 4 4 4 4 12
1 3 3 3 1 1 1 1 3
1 3 3 3 1 1 1 1 3
1 3 3 3 1 1 1 1 3
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 1 1 1 1 1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）