果园里的苹果树整齐的排列成N行M列，每棵树上结了不同数量的苹果，现在请你按照以下规则摘苹果，使得总共采摘苹果的数量最大： 不能同时摘任意相邻的两棵树上的苹果（A果树在B果树四周的8个位置时，认为A和B相邻）； 一棵树上的苹果当然可以全部摘光。
第一行有一个正整数 T，表示了有 T 组数据。 对于每一组数据，第一行有两个正整数 N 和 M，表示了有 N 行 M 列果树。 接下来 N 行，每行 M 个非负整数，表示每棵苹果树上的苹果数量。
共 T 行，每行一个非负整数，输出所求得的答案。
【输入样例】 3 4 4 67 75 63 10 29 29 92 14 21 68 71 56 8 67 91 25 2 3 87 70 85 10 3 17 3 3 1 1 1 1 99 1 1 1 1 【输出样例】 271 172 99
对于100%的数据，1≤N,M≤6，1≤T≤10。