Реверс LLM - 2

В этой задаче на проверку необходимо сдать текстовый файл, соответствующий формату вывода. Входные данные расположены в файле "b2.txt" архива со входными данными. Скачать его можно, нажав на стрелку, расположенную в правом верхнем углу рядом с кнопкой «объявления жюри».

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

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

B i , j = k = 1 N ( A i , k × A k , j ) m o d 2 B_{i, j} = \sum_{k=1}^N (A_{i, k} \times A_{k, j}) mod 2 , где m o d mod  — это операция взятия остатка.

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

Формат ввода

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

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

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

Формат вывода

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

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

Примечания

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

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

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