Блокировка экрана на смартфоне может быть реализована с помощью рисунка. Рисунок для разблокировки имеет \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 The first line of the input contains an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{5}) denoting the number of test cases. After that \textbf{N} test cases follow. Each test case contains a single integer \textbf{m} (\textbf{2} ≤ \textbf{m} ≤ \textbf{6}) denoting a size of an \textbf{m}x\textbf{m} modified mesh graph. \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 In the above sample input, there is only \textbf{1} test case (\textbf{N = 1}). For example, in the first test case there are \textbf{16 }different spanning trees for \textbf{m = 2}. These spanning trees are listed below. Note that your program is NOT required to draw all possible patterns. \includegraphics{https://static.e-olymp.com/content/81/81385946848e70a51c6eecf16e65abc568db48d7.jpg}