color II

Problem Description

You are given an undirected graph with n vertices numbered 0 through n-1. Obviously, the vertices have 2^n - 1 non-empty subsets. For a non-empty subset S, we define a proper coloring of S is a way to assign each vertex in S a color, so that no two vertices in S with the same color are directly connected by an edge. Assume we've used k different kinds of colors in a proper coloring. We define the chromatic number of subset S is the minimum possible k among all the proper colorings of S. Now your task is to compute the chromatic number of every non-empty subset of the n vertices.

Input

First line contains an integer t. Then t testcases follow. In each testcase: First line contains an integer n. Next n lines each contains a string consisting of '0' and '1'. For 0<=i<=n-1 and 0<=j<=n-1, if the j-th character of the i-th line is '1', then vertices i and j are directly connected by an edge, otherwise they are not directly connected. The i-th character of the i-th line is always '0'. The i-th character of the j-th line is always the same as the j-th character of the i-th line. For all testcases, 1<=n<=18. There are no more than 100 testcases with 1<=n<=10, no more than 3 testcases with 11<=n<=15, and no more than 2 testcases with 16<=n<=18.

Output

For each testcase, only print an integer as your answer in a line. This integer is determined as follows: We define the identity number of a subset S is $id(S)=\sum_{v\in S} 2^v$. Let the chromatic number of S be $f_{id(S)}$. You need to output $\sum_{1<=id(S)<=2^n - 1} f_{id(S)} \times 233^{id(S)} \mod 2^{32}$.

Sample Input

2
4
0110
1010
1101
0010
4
0111
1010
1101
1010

Sample Output

1022423354
2538351020

Hint

For the first test case, ans[1..15]= {1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3}

Author

学军中学

Source

2016 Multi-University Training Contest 8