题目描述

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

输入格式

第一行包含一个正整数 $T$ ($1≤T≤20$)，表示测试数据的组数。

每组数据第一行包含一个正整数 $n$ ($1≤n≤60$)，表示矩阵的大小。

接下来 $n$ 行，每行一个长度为 $n$ 的 $01$ 串，第 $i$ 行第 $j$ 列表示 $M_{i,j}$ ($1≤i,j≤n$)。

输出格式

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

输入样例

1
9
010010000
001000001
000100000
010000000
000001000
000000100
000000010
000010001
000000000

输出样例

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