You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

出完P1139的Zoey学姐心力交瘁，题面和数据一直出问题，她不想再看到香飘飘三个字了

Description

现在Zoey学姐要回家，走到一个n*m的矩阵前，入口是最左上角，出口是最右下角，由于学姐太过疲惫，她只想向下或向右走（方向是相对于整个矩阵），矩阵的每一小格内有x个香飘飘，每走过一个小格Zoey都必须拿走格内的香飘飘，已知矩阵情况，请你帮Zoey算出她最少可以拿多少杯香飘飘离开矩阵。

Format

Input

第一行输入一个正整数T代表有T组数据（0≤T≤10），接下来有T组数据 对于每组数据，第一行输入两个正整数n 和m（n为行数m为列数）接下来是n行数据，每行数据有m个x，且x为整型，为每个格子内香飘飘数（0≤n，m，x<=100）。

Output

对于每组数据输出一个整数，为Zoey学姐最少带走的香飘飘数。

Samples

2
3 4
4 2 3 1 
3 5 4 9 
4 9 4 9 
3 4
7 9 6 8 
2 2 1 8 
6 2 5 0 

26
17

Limitation

1s, 1024KiB for each test case.