그래프 색칠 2

$n$개의 정점이 $0$부터 $n - 1$까지 번호가 붙은 무방향 그래프가 주어진다. 정점 집합의 공집합이 아닌 부분집합은 당연히 $2^n - 1$개이다. 공집합이 아닌 부분집합 $S$의 적절한 색칠은 $S$의 각 정점에 색을 부여하되, $S$ 안에서 같은 색을 가진 두 정점이 간선으로 직접 연결되지 않도록 하는 방법이다. 적절한 색칠에서 서로 다른 색을 $k$가지 사용했다고 하자. 부분집합 $S$의 색칠수는 $S$의 모든 적절한 색칠 중 가능한 $k$의 최솟값이다.

이제 $n$개 정점의 공집합이 아닌 모든 부분집합의 색칠수를 계산해야 한다.

첫째 줄에 정수 $T$가 주어진다. 그다음 $T$개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫째 줄에는 정수 $n$이 주어진다. 그다음 $n$개의 줄에는 각각 '0'과 '1'로 이루어진 문자열이 주어진다. $0 \le i \le n - 1$이고 $0 \le j \le n - 1$일 때, $i$번째 줄의 $j$번째 문자가 '1'이면 정점 $i$와 $j$가 간선으로 직접 연결되어 있고, 그렇지 않으면 연결되어 있지 않다.

$i$번째 줄의 $i$번째 문자는 항상 '0'이다. $j$번째 줄의 $i$번째 문자는 항상 $i$번째 줄의 $j$번째 문자와 같다.

모든 테스트 케이스에 대해 $1 \le n \le 18$이다. $1 \le n \le 10$인 테스트 케이스는 $100$개 이하이고, $11 \le n \le 15$인 테스트 케이스는 $3$개 이하이며, $16 \le n \le 18$인 테스트 케이스는 $2$개 이하이다.

각 테스트 케이스마다 정수를 한 줄에 하나씩 출력한다. 이 정수는 다음과 같이 정해진다. 부분집합 $S$의 식별 번호를 $\mathit{id} (S) = \sum\_{v \in S} 2^v$로 정의한다. $S$의 색칠수를 $f\_{\mathit{id} (S)}$라 하자. 다음 값을 출력해야 한다. $\left(\sum\limits\_{\mathit{id} (S) = 1}^{2^n - 1} f\_{\mathit{id} (S)} \cdot 233^{\mathit{id} (S)}\right) \bmod 2^{32}\text{.}$

첫 번째 테스트 케이스에서 $ans\[1..15] = \\{1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3\\}$이다.