DCEPC502 - Just Like the Good Old Days

Sheldon and Penny are neighbours. Penny really likes grid games so Sheldon develops a new grid based game for Penny. The game consists of a M×N grid (M rows, N columns) and an infinite number of black and white knights. The grid has some open and some closed blocks. In the beginning of the game each player chooses his colour of knight. The rule says that each player on his turn can place his knight on any of the open blocks such that none of his knights attack any knight of other colour (he may attack any knight of the same colour). You are given a M×N grid. Specify the maximum number of knights (black and white) which can be placed on the grid. The game stops when any one player cannot place any more knights.

Note: In one turn, Knight can move exactly two squares horizontally and one square vertically, or two squares vertically and one square horizontally.

Input

First line specifies T, the number of test cases.

First line of each test case gives M and N separated by a single space

This is followed by a grid of size M×N consisting of ‘.’ And ‘#’. Each ‘.’ represents an open position and each ‘#’ represents closed position.

Output

Output 1 line for each test case giving the maximum possible value of knights that can be placed.

Constraints

1 <= T <= 5
1 <= M, N <= 10
0 <= Number of open positions "." <= 10

Example

Input:
2
3 3
...
...
...
3 3
...
.#.
...

Output:
7
6

Added by:dce coders
Date:2012-04-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2012-04-26 13:35:44 dce coders
Updated. M rows, N columns.
2012-04-25 12:52:54 :D
Could you specify witch of M and N stand for rows and columns count? My program was written to work both ways, but it would be nice to clarify.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.