Justice for All

Time limit1sMemory limit128 MB

Summary

Given a k x k 0/1 trust matrix (k up to 20), count the number of perfect matchings between knights and horses, i.e. the permanent of the matrix.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics
Solved: No attempts yet

Problem

Ardenia is going to war. Its celebrated military unit is made up of exactly $k$ knights and $k$ horses. A mutual trust relation is fixed between them: we say that knight $i$ trusts horse $j$ (and, symmetrically, horse $j$ trusts knight $i$ ). One horse may trust any number of knights, and one knight may trust any number of horses.

Before every battle the unit forms an assignment: each knight is given a single horse that the knight trusts, and no two knights may be given the same horse. In other words, an assignment is a one-to-one pairing of all $k$ knights with all $k$ horses that respects the trust relation.

Two different battles must use different assignments, and the unit is willing to fight one battle for every distinct valid assignment. Given the trust relation, determine how many battles the unit is prepared for.

Input

The first line contains an integer $Z$ ( $1 \le Z \le 100$ ), the number of test cases.

Each test case begins with a line containing an integer $k$ ( $1 \le k \le 20$ ), the number of knights, which is equal to the number of horses. The next $k$ lines each contain exactly $k$ characters, every character being 0 or 1. The $j$ -th character of the $i$ -th line is 1 if knight $i$ trusts horse $j$ , and 0 otherwise.

Output

For each test case, print a single line containing one integer: the number of battles the unit is prepared for, i.e. the number of distinct valid assignments. This value is at most $20!$ , so it always fits in a signed 64-bit integer.

Examples2

Example 1
Input
```
2
2
11
11
3
110
101
111
```
Expected output
```
2
3
```
Example 2
Input
```
1
4
1111
1111
1111
1111
```
Expected output
```
24
```