Description

在Dota（古代防御）游戏中，普吉的队友给了他一个新的任务“吃树”。这些树都是大小为n×m的矩形单元格，每个单元格要么只有一棵树，要么什么都没有。普吉需要做的是“吃掉”单元格里的所有树。他必须遵守几条规则：

①必须通过选择一条回路来吃掉这些树，然后吃掉所选回路中的所有树；

②不包含树的单元格是不可被访问的，例如，选择的回路通过的每个单元格都必须包含树，当选择回路时，回路上单元格中的树将消失；

③可以选择一个或多个回路来吃这些树。

有多少方法可以吃这些树？

在下图中为$n=6$和$m=3$给出了三个样本（灰色方块表示在单元格中没有树，粗体黑线表示所选的回路）。

Format

Input

输入的第$1$行是测试用例数$T（T≤10）$。每个测试用例的第1行都包含整数n和$m（1≤n,m≤11）$。在接下来的$n$行中，每行都包含$m$个数字（$0$或$1$），$0$表示没有树的单元格，$1$表示只有一棵树的单元格。

Output

对每个测试用例，都单行输出有多少种方法可以吃这些树，保证不超过$263-1$。

Samples

2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1

Case 1: There are 3 ways to eat the trees.
Case 2: There are 2 ways to eat the trees.

来源

HDU1693