Реверс LLM
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Большие языковые модели (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 балла.