给你一个无向图，包含 $n$ 个顶点，编号为 $0$ 到 $n - 1$。显然，顶点集有 $2^n - 1$ 个非空子集。对于一个非空子集 $S$，$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$ 的标识数（identity number）为 $id(S) = \sum_{v \in S} 2^v$。设 $S$ 的色数为 $f_{id(S)}$。你需要输出：

$$\left( \sum_{id(S)=1}^{2^n-1} f_{id(S)} \cdot 233^{id(S)} \right) \bmod 2^{32}$$

样例

输入样例 1

2
4
0110
1010
1101
0010
4
0111
1010
1101
1010

输出样例 1

1022423354
2538351020

说明

对于第一组测试数据，$ans[1..15] = \{1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3\}$。