Реверс LLM - 1

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

В этой задаче на проверку необходимо сдать программу, которая будет решать поставленную задачу.

Большие языковые модели (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 10 1 \le T \le 10 ) — количество матриц, для которых нужно найти квадратный корень.

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

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

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

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

Если вы не можете определить квадратный корень для какой-либо матрицы — выведите N N строк, состоящих из N 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 балла.