#929Number Maze

Consider a number maze represented as a two dimensional array of numbers comprehended between 0 and 9, as exemplified below. The maze can be traversed following any orthogonal direction (i.e., north, south, east and west). Considering that each cell represents a cost, then finding the minimum cost to travel the maze from one entry point to an exit point may pose you a reasonable challenge. Your task is to find the minimum cost value to go from the top-left corner to the bottom-right corner of a given number maze of size N ×M where 1 ≤ N, M ≤ 999 . Note that the solution for the given example is 24.

Input

The input file contains several mazes. The first input line contains a positive integer defining the number of mazes that follow. Each maze is defined by: one line with the number of rows, N ; one line with the number of columns, M ; and N lines, one per each row of the maze, containing the maze numbers separated by spaces.

Output

For each maze, output one line with the required minimum value.

2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5

24
15