题目背景

HDU1693：Eat the Trees

题目描述

给出 $n \times m$ 的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？

输入格式

每个测试点多组数据。第一行一个正整数 $T$，表示有 $T$ 组数据。

对于每组数据：

第 $1$ 行，两个整数 $n,m\ (2 \le n,m \le 12)$。

从第 $2$ 行到第 $n+1$ 行，每行 $m$ 个数字（$1$ 或者 $0$），$1$ 表铺线，$0$ 表不铺线。

输出格式

每组数据输出一个整数，表示方案数。

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

3
2