Background

HDU1693: Eat the Trees

Problem Description

Given an $n \times m$ grid, some cells cannot be filled with lines, and all other cells must be filled. Multiple closed loops can be formed. Ask how many different ways there are to fill the grid?

Input Format

Multiple test cases per input file. The first line contains a positive integer $T$, meaning there are $T$ test cases.

For each test case:

Line $1$: two integers $n, m\ (2 \le n, m \le 12)$.

Lines $2$ to $n + 1$: each line contains $m$ digits ($1$ or $0$). $1$ means this cell must be filled with lines, and $0$ means this cell is not filled with lines.

Output Format

For each test case, output one integer, representing the number of valid ways. It is guaranteed that the answer is less than $2^{63}$.

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

Hint

Translated by ChatGPT 5