摘花生

题目描述

给定一个 $R \times C$ 的网格，每个格子里有若干颗花生。你需要从左上角出发，每次只能向右或向下移动，最终到达右下角。每经过一个格子，就能收集该格子的所有花生。请计算你最多能收集到多少颗花生。

输入格式

第一行：一个整数 $T$（$1 \le T \le 100$），表示测试数据的组数。

对于每组数据：

1. 第一行：两个整数 $R$ 和 $C$（$1 \le R,C \le 100$），分别表示网格的行数和列数。
2. 接下来 $R$ 行：每行包含 $C$ 个非负整数 $M$（$0 \le M \le 1000$），表示对应格子里的花生数量。

输出格式

对于每组数据，输出一行一个整数，表示能收集到的最大花生数。

样例

输入

2
2 2
1 1

输出

3 4
2 3
2 3 4
1 6 5

8
16