Большие языковые модели (Large language model, LLM) в своей основе имеют операцию умножения квадратных матриц. Вася узнал, что в одной из популярных LLM используется возведение в квадрат квадратных 0-1 матриц. Квадратная 0-1 матрица — это двумерный массив

Большие языковые модели (Large language model, LLM) в своей основе имеют операцию умножения квадратных матриц. Вася узнал, что в одной из популярных LLM используется возведение в квадрат квадратных 0-1 матриц.

Квадратная 0-1 матрица — это двумерный массив размером
N
×
N
N×N, состоящий из чисел 0 и 1. В результате возведения матрицы в квадрат получается квадратная матрица того же размера
B
=
A
2
B=A
2
, элементы которой вычисляются по следующей формуле:

B
i
,
j
=
∑
N
k
=
1
(
A
i
,
k
×
A
k
,
j
)
m
o
d
2
B
i,j
​
=∑
k=1
N
​
(A
i,k
​
×A
k,j
​
)mod2, где
m
o
d
mod — это операция взятия остатка.

Васе удалось получить результирующие матрицы
B
B. Для создания своей модели он хочет провести реверс-инжиниринг и найти такую матрицу
A
A, что
B
=
A
2
B=A
2
. Помогите ему.

Формат ввода
В первой строке вводится число
T
T (
1
≤
T
≤
25
1≤T≤25) — количество матриц, для которых нужно найти квадратный корень.

Далее следует
T
T блоков с описанием матрицы.

В первой строке каждого блока содержится число
N
N (
2
≤
N
≤
5
2≤N≤5) — размер матрицы. В следующих
N
N строках содержится по
N
N чисел 0 и 1, задающих матрицу.

Формат вывода
Выведите
T
T матриц, являющихся квадратным корнем заданной. Разделяйте матрицы пустой строкой.

Если вы не можете определить квадратный корень для какой-либо матрицы — выведите
N
N строк, состоящих из
N
N нулей, где
N
N соответствует размеру исходной матрицы.

Примечания
Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Во время тура проверяется, что файл содержит
T
T матриц правильного размера и матрицы состоят из чисел 0 и 1.

Каждая верно найденная матрица оценивается в 2 балла.