Bob wants to take revenge from Peter. So he thinks of stealing apples form Peter's garden. But Peter is also clever. He has put sensors in garden in order to detect stealing. Still Bob has figured out a way such that he will not be caught.

Peter's garden can be represented as a 2 dimensional matrix of size N x M where each cell (i,j) contains an integer value which denotes the number of apples Bob can pick from that cell. Cell(i,j) may have a sensor which is represented by "#"(see sample test cases).

Bob will follow the following rules in order not to get caught.

1 - If Bob is facing right at cell (i,j) he can move to cell(i,j+1) facing right or he can move to cell(i+1,j) and turn his face left.

2 - If Bob is facing left at cell (i,j) he can move to cell(i,j-1) facing left or he can move to cell(i+1,j) and turn his face right.

3 - If cell(i,j) contains a sensor then , Bob cannot go to that cell.

If Bob does not follow above rules , then he will be caught.

Bob will start from upper left corner facing right and collect apples from Peter's garden. Find the maximum number of apples that Bob can collect without being caught.

Note: Bob can come out of the garden only once.

Input:

First line contains an integer t - number of test cases.

First line of each test case contains two integers N and M - dimensions of the garden.

Next N lines contains a string of M length - denoting the number of apples at cell(i,j) or a sensor("#").

Output:

For each test case , print the maximum number of apples that Bob can collect without being caught in a new line.

Constraints:

1<=t<=50

1 <= N,M <= 2000

0 <= number of apples in each cell <= 9