Большие языковые модели (Large language model, LLM) в своей основе имеют операцию умножения квадратных матриц. Вася узнал, что в одной из популярных LLM используется возведение в квадрат квадратных 0-1 матриц.
Квадратная 0-1 матрица — это двумерный массив размером $$$N \times N$$$, состоящий из чисел 0 и 1. В результате возведения матрицы в квадрат получается квадратная матрица того же размера $$$B = A^2$$$, элементы которой вычисляются по следующей формуле:
$$$B_{i, j} = \sum_{k=1}^N (A_{i, k} \times A_{k, j}) mod 2$$$, где $$$mod$$$ — это операция взятия остатка.
Васе удалось получить результирующие матрицы $$$B$$$. Для создания своей модели он хочет провести реверс-инжиниринг и найти такую матрицу $$$A$$$, что $$$B = A^2$$$. Помогите ему.
В первой строке вводится число $$$T$$$ ($$$1 \le T \le 10$$$) — количество матриц, для которых нужно найти квадратный корень.
Далее следует $$$T$$$ блоков с описанием матрицы.
В первой строке каждого блока содержится число $$$N$$$ ($$$2 \le N \le 4$$$) — размер матрицы. В следующих $$$N$$$ строках содержится по $$$N$$$ чисел 0 и 1, задающих матрицу.
Выведите $$$T$$$ матриц, являющихся квадратным корнем заданной. Разделяйте матрицы пустой строкой.
Если вы не можете определить квадратный корень для какой-либо матрицы — выведите $$$N$$$ строк, состоящих из $$$N$$$ нулей, где $$$N$$$ соответствует размеру исходной матрицы.
2 3 1 0 0 0 1 0 0 0 1 3 0 1 0 0 1 0 0 1 0
0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждая верно найденная матрица оценивается в 2 балла.