题目描述

Hello Kitty来到一片R行C列的花生地。每个位置种着一株花生苗，经过时可以摘下其全部花生。

她从西北角（左上角）进入，从东南角（右下角）离开，每次只能向东或向南移动一格。求最多能摘到多少颗花生，包括起点和终点的花生。

输入格式

第一行整数T，表示数据组数。每组第一行两个整数R、C，接下来R行，每行C个整数，表示每株花生苗的花生数量。

输出格式

每组输出一行，表示最多能摘到的花生数量。

样例

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

8
16

数据范围

1≤T≤100，1≤R,C≤100，每株花生数量在0至1000之间。