G. Волшебный квадрат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Aquamoon есть квадратик Рубика, который можно представить как матрицу размера $$$n \times n$$$, причём элементы матрицы составляют перестановку чисел $$$1, \ldots, n^2$$$.

Aquamoon можно производить над матрицей следующие операции:

  • Сдвиг строки, т.е. сдвиг некоторой строки матрицы на несколько позиций (хотя бы на $$$1$$$ и не более чем на $$$n-1$$$) вправо. Элементы, выходящие за правую границу матрицы, сдвигаются в начало строки. Так, например, сдвиг строки $$$\begin{pmatrix} a & b & c \end{pmatrix}$$$ на $$$2$$$ позиции превратит её в $$$\begin{pmatrix} b & c & a \end{pmatrix}$$$;
  • Сдвиг столбца, т.е. сдвиг некоторого столбца матрицы на несколько позиций (хотя бы на $$$1$$$ и не более чем на $$$n-1$$$) вниз. Элементы, выходящие за нижнюю границу матрицы, сдвигаются в начало столбца. Так, например, сдвиг столбца $$$\begin{pmatrix} a \\ b \\ c \end{pmatrix}$$$ на $$$2$$$ позиции превратит его в $$$\begin{pmatrix} b\\c\\a \end{pmatrix}$$$.

Строки матрицы пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$n$$$ слева направо. Клетку на пересечении $$$x$$$-й строки и $$$y$$$-го столбца обозначим как $$$(x, y)$$$.

Aquamoon может выполнить несколько (возможно, ноль) операций, но она должна выполнять следующие ограничения:

  • каждая строка и каждый столбец могут быть сдвинуты не более чем по одному разу;
  • каждое число матрицы может быть сдвинуто не более чем дважды;
  • итоговые смещения любых двух чисел, сдвинутых дважды, должны быть попарно различны. Формально, пусть числа $$$a$$$ и $$$b$$$ были сдвинуты по два раза. Пусть $$$a$$$ изменило свою позицию с $$$(x_1,y_1)$$$ на $$$(x_2,y_2)$$$, а $$$b$$$ изменило позицию с $$$(x_3,y_3)$$$ на $$$(x_4,y_4)$$$. Тогда $$$x_2-x_1 \not\equiv x_4-x_3 \pmod{n}$$$ или $$$y_2-y_1 \not\equiv y_4-y_3 \pmod{n}$$$.

Aquamoon интересно, сколькими способами она может преобразовать исходное состояние квадратика в некоторое заданное конечно состояние. Два способа считаются различными, если последовательности применяемых операций в них различны. Поскольку ответ может быть очень большим, выведите его по модулю modulo $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3\le n \le 500$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержится $$$n$$$ целых чисел $$$a_{i1}, \ldots, a_{in}$$$, которые задают $$$i$$$-ю строчку исходной матрицы ($$$1 \le a_{ij} \le n^2$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержится $$$n$$$ целых чисел $$$b_{i1}, \ldots, b_{in}$$$, которые задают $$$i$$$-ю строчку конечной матрицы ($$$1 \le b_{ij} \le n^2$$$).

Гарантируется, что элементы исходной матрицы, а также элементы конечной матрицы, образуют перестановки чисел $$$1, \ldots, n^2$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

Выходные данные

Для каждого набора входных данных, если возможно преобразовать начальное состояние в конечное, соблюдая все условия, то выведите одно число — число способов это сделать по модулю $$$998\,244\,353$$$.

Если решения не существует, выведите одно целое число $$$0$$$.

Пример
Входные данные
4
3
1 2 3
4 5 6
7 8 9
7 2 3
1 4 5
6 8 9
3
1 2 3
4 5 6
7 8 9
3 2 1
6 5 4
9 7 8
3
1 2 3
4 5 6
7 8 9
7 8 1
2 3 4
5 6 9
3
1 2 3
4 5 6
7 8 9
3 8 4
5 1 9
7 6 2
Выходные данные
1
0
0
4
Примечание

В первом наборе входных данных единственный способ преобразовать исходную матрицу в конечную — сдвинуть вторую строку на $$$1$$$ вправо, а затем сдвинуть первый столбец на $$$1$$$ вниз.

Во втором наборе входных данных можно показать, что нет ни одного корректного способа преобразовать матрицу, так что ответ равен $$$0$$$.