#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>
#include <ctime>
 
using namespace std;
 
const int N = 31;
const int MAXSIZE = 500000;
 
int bitmasks[MAXSIZE];
int next_fib[MAXSIZE][2];
int Fib[N+1], cnt = 0;
 
int getValue( int x ) {
	int result = 0;
	for( int i = 0; i <= N; i ++ )
		if( x & (1 << i) )
			result += Fib[i];
	return result;
}
 
void go( int idx, int cur ) {
	if( idx > N ) return;
	int g = getValue(cur);
	bitmasks[g] = cur;
	next_fib[g][0] = getValue((cur << 1));
	next_fib[g][1] = getValue((cur << 1) + 1);
	if( idx != N ) {
		if( cur & 3 )
			go( idx + 1, cur * 2 );
		else {
			go( idx + 1, cur * 2 );
			go( idx + 1, cur * 2 + 1 );
		}
	} else {
		cnt ++;
	}
}
 
void pre_process() {
	int cl = clock();
	Fib[0] = 1;
	Fib[1] = 2;
	Fib[2] = 3;
	for( int i = 3; i <= N; i ++ )
		Fib[i] = Fib[i-1] + Fib[i-3];
	go(0, 0);
	cerr << Fib[N] << " " << cnt << endl;
	cerr << (clock() - cl) * 1. / CLOCKS_PER_SEC << endl;
}
 
inline int GetBitmask( int max_n, int i, int j ) {
	int result = i + j * max_n;
	return result;
}
 
inline bool isset( int n, int i ) {
	return n & (1 << i);
}
 
string binary( int n ) {
	string s;
	for( int i = 0; i < 4; i ++ )
		if( n & (1 << i) )
			s = string("1") + s;
		else
			s = string("0") + s;
	return s;
}
 
int t, n, m, benefit[N][N];
int mat[2][MAXSIZE];
 
int solve() {
	memset(mat, 0, sizeof mat);
	int idx = 0;
	for( int x = n - 1; x >= 0; x -- ) {
		for( int y = m - 1; y >= 0; y -- ) {
			int pidx = 1 - idx;
			for( int i = 0; i < Fib[y]; i ++ )
				for( int j = 0; j < Fib[m - y]; j ++ ) {
					int bm = GetBitmask(Fib[y], i, j);
					mat[idx][bm] = 0;
 
					// Try selecting
					if(!isset(bitmasks[i], 0) && !isset(bitmasks[i], 1) && !isset(bitmasks[j], m - y - 1)) {
						if( y == m - 1 )
							mat[idx][bm] >?= benefit[x][y] + mat[pidx][GetBitmask(Fib[0], 0, next_fib[i][1])];
						else {
							int tbm = isset(bitmasks[j], m - y - 1) ? (j - Fib[m - y - 1]) : j;
							mat[idx][bm] >?= benefit[x][y] + mat[pidx][GetBitmask(Fib[y + 1], next_fib[i][1], tbm)];
						}
					}
 
					// Try Ignoring
					if( y == m - 1 )
						mat[idx][bm] >?= mat[pidx][GetBitmask(Fib[0], 0, next_fib[i][0])];
					else {
						int tbm = isset(bitmasks[j], m - y - 1) ? (j - Fib[m - y - 1]) : j;
						mat[idx][bm] >?= mat[pidx][GetBitmask(Fib[y + 1], next_fib[i][0], tbm)];
					}
				}
			idx = pidx;
		}
	}
	return mat[1-idx][0];
}
 
int main() {
	int sc = clock();
	freopen( "grid.in", "r", stdin );
	freopen( "grid.out", "w", stdout);
	pre_process();
	cerr << "Done" << endl;
	for( scanf("%d", &t); t--; ) {
		int cl = clock();
		scanf("%d %d", &n, &m);
		for( int i = 0; i < n; i ++ )
			for( int j = 0; j < m; j ++ )
				scanf("%d", &benefit[i][j]);
		printf("%d\n", solve());
		cerr << (clock() - cl) * 1. / CLOCKS_PER_SEC << endl;
	}
	cerr << (clock() - sc) * 1. / CLOCKS_PER_SEC << endl;
	return 0;
}