cho.sh

Closet Room (Large)

Place the maximum number of 2-cell closets, each needing an empty door tile, on a grid with pillars so every door tile stays connected to the entrance.

Hard8Dynamic programmingGraphBit manipulationNo attempts yetTime limit5sMemory limit512 MB

Problem

Pascal, the president of a clothing company, rented a warehouse of width WW and depth HH to store leftover stock, and decided to install as many closets in it as he can. The floor of the warehouse is covered by W×HW \times H tiles of size 1×11 \times 1, and the entrance door touches exactly one tile on the outer border. A few pillars stand inside the warehouse, and there may be none at all.

A closet is a rectangular box of width 2 and depth 1, so it covers exactly two tiles. One of its two faces of width 2 carries the door, and when you look straight at that face, the door takes up the left half.

A robot carries the clothes out. For every closet there must be a route the robot can walk from the entrance of the warehouse to the tile right in front of that closet's door. The robot has size 1×11 \times 1 and moves from a tile to one of the four tiles next to it. It cannot step on a tile covered by a closet or by a pillar.

The president is meticulous, so he ordered that every closet sit on exactly two tiles. That leaves exactly four ways to place one closet. C is the body of the closet, and X is the tile that must be kept empty so the door can open. . is any other tile.

....
.CC.
.X..
....

....
..X.
.CC.
....

....
.XC.
..C.
....

....
.C..
.CX.
....

The X tile has to be inside the warehouse, it must carry no pillar, and no closet may cover it. The robot starts on the tile that touches the entrance door and must be able to walk from there to the X tile of every closet. Two closets may use the same X tile.

Find the largest number of closets the president can install in the warehouse.

Input

The first line has the number of test cases TT. Then TT test cases follow.

The first line of each test case has the depth HH and the width WW of the warehouse, separated by a space. Then HH lines follow, each a string of length WW.

The jj-th character ci,jc_{i,j} of the ii-th line describes the state of tile (i,j)(i, j). It is D if the tile touches the entrance door, X if a pillar stands on it, and . if neither holds. D appears exactly once in each test case.

Constraints

  • 1≤T≤1001 \le T \le 100
  • 1≤H≤301 \le H \le 30
  • 1≤W≤51 \le W \le 5

Output

For each test case print one line in this format.

Case #X: Y

XX is the test case number starting from 1, and YY is the largest number of closets that can be installed under the rules.