Screen lock on a smart phone can be secured with pattern. Unlock pattern may have \textbf{9 }nodes on the \textbf{3}×\textbf{3 }grid. In this problem, we modify this arrangement slightly such that the grid size can be varied from \textbf{2}×\textbf{2 }to \textbf{m}×\textbf{m}, and only a limited number of connections between adjacent nodes are permitted. Let call this a modified mesh graph \textbf{G }and \textbf{V }is a set of vertices (nodes) and \textbf{E }is a set of edges (connections). Examples of \textbf{2}×\textbf{2}, \textbf{3}×\textbf{3} and \textbf{4}×\textbf{4 }modified mesh graphs are given in the figures below. Note that the corner vertices have \textbf{3 }connections at most, while the middle vertices can have up to \textbf{8 }connections. Only a connection to adjacent vertices is allowed, a constraint of the problem. \includegraphics{https://static.e-olymp.com/content/e1/e11aec12100eaa413f4317a90e4caa1b4d6f681a.jpg} We define a spanning tree in our problem as a collection of lines in the graph forming no closed loops, containing a path between any two points of the graph covering \textbf{m^2} = \textbf{n }vertices and \textbf{n} -- \textbf{1 }edges. Spanning trees in a graph can have many shapes or patterns. To calculate a number of spanning trees in \textbf{G}, let \textbf{G }be a graph with vertices labeled \textbf{v_1}, ..., \textbf{v_n}. We form an \textbf{n}×\textbf{n }matrix tree \textbf{T} = \textbf{\[t_ij\]} as follows. \begin{itemize} \item If \textbf{i} = \textbf{j}, then \textbf{t_ii} is the number of lines to \textbf{v_i} in the graph. \item If \textbf{i }≠ \textbf{j}, then \textbf{t_ij} = \textbf{0} if there is no line between \textbf{v_i} and \textbf{v_j} in \textbf{G}. \item If \textbf{i }≠ \textbf{j}, then \textbf{t_ij} = \textbf{-1} if there is a line between \textbf{v_i} and \textbf{v_j} in \textbf{G}. \end{itemize} Then, the number of spanning trees in \textbf{G }is given by \textbf{cofactor of a_ij} = \textbf{(-1)^\{i+j\}M_ij} where \textbf{M_ij} is the determinant of the \textbf{(n-1) }× \textbf{(n-1)} matrix obtained by deleting row \textbf{i }and column \textbf{j }of the matrix tree \textbf{T}. Evaluate any cofactor of \textbf{T }yields the same result. \textit{\textbf{Example 1}}: A matrix tree \textbf{T }of \textbf{2}×\textbf{2 }modified mesh graph is \includegraphics{https://static.e-olymp.com/content/cb/cb929d630c281cfe475de11e7a0949230920981d.jpg} Evaluate any cofactor of \textbf{T}. For example, covering up row \textbf{1 }and column \textbf{1}, we have \includegraphics{https://static.e-olymp.com/content/6f/6fadc692390a52c40ae96217b6ec1e20476336a6.jpg} Therefore, a number of spanning tree is \textbf{16}. \textit{\textbf{Example 2}}: A matrix tree \textbf{T }of \textbf{3}×\textbf{3 }modified mesh graph is \includegraphics{https://static.e-olymp.com/content/b0/b0dfdcea2151c95f0842404984ab84cc4482d2db.jpg} Evaluate any cofactor of \textbf{T }will yield the same value which is the number of spanning trees. Hint: Determinant calculation using elementary row operation method: To calculate a determinant you need to transform an original matrix into an upper triangular matrix (all elements below main diagonal are zero). Reduce the matrix to row echelon form using elementary row operations so that all the elements below diagonal are zero. Then multiply the main diagonal elements of a matrix to get the determinant value. Your task is to write a program to find the number of spanning trees for a given size \textbf{m}×\textbf{m} of a modified mesh graph. \InputFile The first line 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} = \textbf{1}). For example, in the first test case there are \textbf{16 }different spanning trees for \textbf{m} = \textbf{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}