说明

在央视娱乐节目购物街中，有这样一个环节，货架上有m×n个方格，在每个方格中各放置1个商品，每个商品都标有价格，嘉宾可以挑选商品，但是选了某一商品，就不能再选它上下左右相邻的商品。最后，挑选出的商品总价最高的人获得胜利。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入货架的行数m和列数n（1<=m,n<=100）。

接下来m行，每行n个数，输入每行每个商品的价值w。（1<=w<=100）。

输出格式

对于每一组输入，输出挑选物品的最大价值。

每组的输出占1行。

样例

2
4 4
10  8   5   2
1   3   9   15
5   10  13  7
24  12  20  14
4 5
12  9   15   4  10
6   2   22   10  8
35   24  3  17  36
20  15  18  14  30

84
158

来源

《趣学算法》7.9节