Coin Collection

Interview

Time limit1sMemory limit128 MB

Summary

A robot walks right or down only from the top-left to the bottom-right of a grid, and we want the most coins it can pick up along the way.

Level: Medium4 of 10
Topics: Dynamic programming, Matrix, Array, Implementation
Solved: No attempts yet

Problem

Coins are placed on the cells of an $n \times m$ board, with at most one coin per cell. A robot starts at the top-left cell of the board and wants to collect as many coins as possible on its way to the bottom-right cell. On each step the robot may move only one cell to the right or one cell down from its current position. Whenever the robot passes through a cell that contains a coin, it always picks the coin up. Determine the maximum number of coins the robot can collect.

The figure below shows an example board.

Input

The first line contains a positive integer $T$ , the number of test sets.

Each test set begins with a line containing two positive integers $n$ and $m$ ( $1 \le n \le 50$ , $1 \le m \le 50$ ), the number of rows and columns of the board. The next $n$ lines each contain $m$ characters; each character is either X for an empty cell or C for a coin.

Output

For each test set, print on its own line the maximum number of coins the robot can collect.

Examples3

Example 1

Input

2
5 7
CXXXXCC
XCCCXXX
XXXXXXC
CXCCXXX
XCXXXCX
4 4
XXXX
CCCC
XXXX
CCCC

Expected output

6
5

Example 2
Input
```
1
1 1
C
```
Expected output
```
1
```
Example 3
Input
```
1
1 5
CCCCC
```
Expected output
```
5
```