Queen Cersei's secret vault is full of gold coins. The floor of the vault is covered with RxC square tiles i.e R rows and C columns of tiles. Each tile has some gold coins.
Being the Queen's loyal servant, you are given the opportunity to go through the vault once and collect as many gold coins as possible.
Following are the rules:
Given the values of R and C, and the number of gold coins on each tile, find out the maximum number of coins you can have when you come out of the vault.
Input:
1st line: T, the number of test cases.
In each of the test cases,
1st line: R and C, the number of rows and columns of tiles in the vault.
Next R lines: ith line specifies the number of gold coins on each tile of the ith row. Each line has C integers, where each integer G is the number of gold coins on that tile. The integers are separated by a space character.
Constraints:
Output:
The output should consist of T lines.
Each line consists of a single integer, which is the maximum possible number of gold coins you can collect from the first row to the last row for the corresponding test case.
4 + 3 + 5 + 1 = 13