Description

wywcgs is good at Graph Theory. Tree has many good property among all kinds of graphs, so wywcgs likes it very much. But many graphs are not trees :( Now wywcgs wants to know how many spanning trees are there in a given graph G. Vertices are all labeled. That is, vertices are considered to be different.

Input

Input contains multiple test cases. The first line is a integer T, the number of test cases. Each case begins with an integer N, with 2 <= N <= 12, denots the number of vertices in the graph. An N*N matrix M follows. The element in row i and column j is 1 if there is an edge between vertex i and j, or 0 otherwise. You are guaranteed that for all i and j we have M[i][j] == M[j][i].

Output

For each test case, output an integer that denotes the number of different spanning trees in G. Two trees are considered different to each other iff one has at least one edge that another one doesn't have.

Sample Input

3 2 1 0 0 1 3 0 1 1 1 0 1 1 1 0 5 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0

Sample Output

0 3 20

Author

wywcgs