Migrated from Lutece 374 Doodle

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

QiQi is a child.

Child always has dreams.

Dreams can be sometimes excellent.

The most excellent dream may be being an artist who enjoys doodling.

QiQi loves doodling since he was a very young boy. After all these years’ hard training, he becomes a very skilled doodler. Today he gets a board which has n rows and m columns. QiQi would like to use his colorful brushes to doodle. Before QiQi starts his work, he plans exactly one color for each cell, meaning that this cell can’t be paint with other colors at any time. Besides, QiQi also plans the least number of times he should doodle for each cell. In each doodle, he can use his brush to doodle some continuous cells vertically or horizontally with the same color.

Now QiQi want to know how many times at least he has to doodle?

Input

The first line of the input is an integer $T$ ($T\leq 20$), which stands for the number of test cases you need to solve.

Every test case begins with $2$ integers $n$, $m$($1\leq n, m\leq 20$) indicating the size of the board. Then n lines follow, each line consists of m integers (each integer is between $1$ and $400$). The $j_{th}$ integer of the $i_{th}$ line represents the color for that cell(different integers stand for different colors). Then n lines follow, each line consists of $m$ integers. The $j_{th}$ integer of the $i_{th}$ line represents the least number of times QiQi would like to doodle for that cell (each integer is between $0$ and $10000$).

Output

For every test case, you should output Case #k: first, where k indicates the case number and starts at $1$. Then output an integer indicating the least number of times QiQi has to doodle.

Samples

2
2 2
1 1
2 2
1 1
1 1
2 2
1 2
2 1
1 1
1 1

Case #1: 2
Case #2: 4

Resources

The 9th UESTC Programming Contest Final