#include <iostream>
#include <map>

struct Point {
	int x, y;
};

using namespace std;

#define maze(x,y) mazeptr[x + y*cols]
#define stepped(x,y) steppedptr[x + y*cols]

int *mazeptr;
bool *steppedptr;
int rows, cols;

multimap<int, Point> cost_map;
multimap<int, Point>::iterator cost_map_iter;

int dirs[4][2] = {
	{ -1,  0 }, // left
	{  0, -1 }, // up
	{  1,  0 }, // right
	{  0,  1 }   // down
	
};

bool valid(Point &p)
{
	return (p.x >= 0 && p.x < cols && p.y >= 0 && p.y < rows);
}

int cost()
{
	int i;
	int total;
	Point cur, p;

	cur.x = cur.y = 0;
	total = maze(cur.x, cur.y);
	cost_map.insert(pair<int, Point>(total, cur));

	for (;;) {
		cost_map_iter = cost_map.begin();
		cur = cost_map_iter->second;		
		total = cost_map_iter->first;

		for (i = 0; i < 4; i++) {
			p.x = cur.x + dirs[i][0];
			p.y = cur.y + dirs[i][1];
			if (p.x == cols - 1 && p.y == rows - 1)
				return total + maze(p.x, p.y);
			if (valid(p) && !stepped(p.x, p.y)) {
				cost_map.insert(pair<int, Point>(total + maze(p.x, p.y), p));
			}
		}

		cost_map.erase(cost_map_iter);
		stepped(cur.x, cur.y) = true;
	}
}

int main(int argc, char *argv[])
{
	int num_mazes, i, j;
	
	cin >> num_mazes;

	while (num_mazes--) {
		cin >> rows >> cols;
		mazeptr = new int[rows * cols];
		steppedptr = new bool[rows * cols];

		for (i = 0; i < rows; i++)
			for (j = 0; j < cols; j++) {
				cin >> maze(j, i);
				stepped(j,i) = false;
			}

		cout << cost() << endl;

		delete mazeptr;
		delete steppedptr;
	}
	
	return 0;
}