#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(t,i,n) for(t i=0;i<n;i++)
#define FIT(t,i,c) for(t::iterator i=c.begin();i!=c.end();i++)

#define MAX_NODES 20

//Macros for handling bit vector current
#define toggle(n,key)	(key^=(1<<(n)))
#define ison(n,key)	(key&(1<<(n)))
//Macros for Bit Vector visited
#define visit(n)	(visited[(n>>3)]|=(1<<(n&7)))
#define is_visited(n)	(visited[(n>>3)]&(1<<(n&7)))

typedef vector<int> _adj_list;

int n;

long long memo[(1<<MAX_NODES)];		//Memoized values of count_ways

char visited[(1<<MAX_NODES)>>3];	//Bit Vector Checks if a particular configuration of current
					//has been visited before or not, for memoization

_adj_list adj[MAX_NODES+2];		//Adjacency list represenatation

long long count_ways(int pos, unsigned long current)
{
	int i;
	long long num_ways = 0;
	if(pos == n) return 1;
	FIT(_adj_list,i,adj[pos])
		if(!ison((*i),current)) {
			toggle((*i),current);
			if(!is_visited(current)) num_ways += count_ways(pos+1, current);
			else num_ways += memo[current];
			toggle((*i),current);
		}
	memo[current]=num_ways;
	visit(current);
	return num_ways;
}

inline bool less_adjacent(_adj_list a, _adj_list b)
{
	if(a.size() < b.size()) return true;
	return false;
}

int main()
{
	int _T;
	scanf("%d", &_T);
	while(_T--) {
		int t;
		unsigned long current = 0;

		memset(adj, 0, sizeof(adj));
		memset(memo, 0, sizeof(memo));
		memset(visited, 0, sizeof(visited));

		scanf("%d", &n);

		FOR(int,i,n) FOR(int,j,n) {
			scanf("%d", &t);
			if(t==1) adj[i].push_back(j);
		}
		sort(adj,adj+n,less_adjacent);

		printf("%lld\n", count_ways(0,current));
	}
	return 0;
}