Блокировка экрана на смартфоне может быть реализована с помощью рисунка. Рисунок для разблокировки имеет \textbf{9 }вершин на сетке \textbf{3}×\textbf{3}. В этой задаче мы изменим размер сетки, позволив ему меняться от \textbf{2}×\textbf{2 }до \textbf{m}×\textbf{m}, и только ограниченное количество соединений разрешено между парами соседних вершин. Назовем такой модифицированный сетевой граф \textbf{G}, \textbf{V} - множество его вершин, \textbf{E} - множество ребер (соединений). Примеры сетевых графов \textbf{2}×\textbf{2}, \textbf{3}×\textbf{3} и \textbf{4}×\textbf{4 }приведены на рисунках. Угловые вершины имеют не более \textbf{3 }соединений, а центральные до \textbf{8 }соединений. Разрешены соединения только между соседними вершинами. \includegraphics{https://static.e-olymp.com/content/e1/e11aec12100eaa413f4317a90e4caa1b4d6f681a.jpg} Определим остовное дерево как набор ребер графа, не образующих цикл, и по которым можно пройти между любыми двумя вершинами. Остовное дерево содержит \textbf{m^2} = \textbf{n }вершин и \textbf{n} -- \textbf{1 }ребро. Остовные деревья в графе могут иметь различные виды и формы. Для вычисления количества остовных деревьев в \textbf{G}, обозначим вершины \textbf{G }метками \textbf{v_1}, ..., \textbf{v_n}. Образуем метрицу \textbf{n}×\textbf{n }дерева \textbf{T} = \textbf{\[t_ij\]} следующим образом. \begin{itemize} \item Если \textbf{i} = \textbf{j}, то \textbf{t_ii} равно числу смежных ребер с \textbf{v_i} в \textbf{G}. \item Если \textbf{i }≠ \textbf{j}, то \textbf{t_ij} = \textbf{0} если не существует ребра между \textbf{v_i} и \textbf{v_j} в \textbf{G}. \item Если \textbf{i }≠ \textbf{j}, то \textbf{t_ij} = \textbf{-1} если существует ребро между \textbf{v_i} и \textbf{v_j} в \textbf{G}. \end{itemize} Тогда количество остовных деревьев в \textbf{G} равно \textbf{cofactor of a_ij} = \textbf{(-1)^\{i+j\}M_ij} где \textbf{M_ij} - детерминант матрицы \textbf{(n-1) }× \textbf{(n-1)} полученной удалением строки \textbf{i }и столбца \textbf{j }из матрицы дерева \textbf{T}. Значение любого алгебраического дополнения \textbf{T }дает один и тот же результат. \textit{\textbf{Пример 1}}: Матрица дерева \textbf{T} для сетевого графа \textbf{2}×\textbf{2 }равна \includegraphics{https://static.e-olymp.com/content/cb/cb929d630c281cfe475de11e7a0949230920981d.jpg} Вычислим алгебраическое дополнение \textbf{T}. Например, исключив строку \textbf{1} и столбец \textbf{1}, получим \includegraphics{https://static.e-olymp.com/content/6f/6fadc692390a52c40ae96217b6ec1e20476336a6.jpg} Поэтому количество остовных деревьев равно \textbf{16}. \textit{\textbf{Пример 2}}: Матрица дерева \textbf{T} сетевого графа \textbf{3}×\textbf{3} имеет вид \includegraphics{https://static.e-olymp.com/content/b0/b0dfdcea2151c95f0842404984ab84cc4482d2db.jpg} Значение любого алгебраического дополнения \textbf{T} одно и то же и равно количеству остовных деревьев. \textbf{Подсказка}: Вычислить определитель можно используя элементарные операции над строками: Следует преобразовать начальную матрицу к верхней треугольной (все элементы ниже главной диагонали равны нулю). Преобразуйте матрицу строка за строкой используя элементарные операции на строках, вследствие чего все элементы ниже главной диагонали станут нулевыми. Затем перемножьте элементы главной диагонали и получите значение определителя. Напишите программу, которая вычислит количество остовных деревьев для модифицированного сетевого графа размера \textbf{m}×\textbf{m}. \InputFile Первая строка содержит количество тестов \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{5}). Каждый тест содержит одно целое число \textbf{m }(\textbf{2 }≤ \textbf{m }≤ \textbf{6}) - размер \textbf{m}x\textbf{m }сетки - графа. \OutputFile For each test case, your program should output the number of spanning trees, which indicates how many patterns of spanning trees there are for a given modified mesh graph. Print out one line per test case, respectively. \Note В примере имеется только один тест (\textbf{n} = \textbf{1}). Для первого теста при \textbf{m} = \textbf{2} имеется \textbf{16 }различных остовных деревьев. Все они перечислены ниже. Вашей программе НЕ требуется рисовать все изображения. \includegraphics{https://static.e-olymp.com/content/81/81385946848e70a51c6eecf16e65abc568db48d7.jpg}