Coin Collection

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.

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.

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