#include<bits/stdc++.h>

using namespace std;

int main()
{
    int count; cin >> count;

    while (count --)
    {
        int m, n; cin >> n >> m;

        vector<vector<int> > edge = vector<vector<int> >(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                    cin >> edge[i][j];

        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                edge[i][j] += max(edge[i - 1][j], edge[i][j - 1]);
        cout << edge[n][m] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int req; cin >> req;

    while (req)
    {
        vector<vector<int> >buff(req, vector<int>(req));

        for (int i = 0; i < req; ++ i)
        {
            buff[i][0] = buff[0][i] = i + 1;
        }
        for (int i = 0; i < req; ++ i)
        {
            int n = req;
            int xpos = i, ypos = 0;
            while (xpos < n && ypos < n) buff[xpos ++][ypos ++] = i + 1;
            xpos = 0, ypos = i;
            while (xpos < n && ypos < n) buff[xpos ++][ypos ++] = i + 1;
        }

        for (int i = 0 ; i < req; ++ i)
        {
            for (int j = 0; j < req; ++ j)
            {
                cout << buff[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        cin >> req;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int st[] = {31,28,31,30,31,30,31,31,30,31,30,31};
int counts[] = {0,0,0,0,0,0,0,0};
int n;

bool Is(int _year)
{
    return (_year % 4 == 0 && _year % 100 != 0) || (_year%100 == 0 && _year % 400 == 0);
}

int main()
{
    cin >> n;
    int flag = 1;
    for (int i = 0; i < n; ++ i) {
        if (Is(1900 + i)) st[1] ++;

        for (int k = 0; k < 12; ++ k)
        {
            for (int j = 1; j <= st[k]; ++ j)
            {
                if (flag == 8) flag = 1;
                if (j == 13) counts[flag] ++;
                flag ++;
            }
        }

        if (Is(1900 + i)) st[1] --;
    }
    for (int i = 6; i <= 7; ++ i)
        cout << counts[i] << " ";
    for (int i = 1; i <= 5; ++ i)
        cout << counts[i] << " ";
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, m; cin >> n >> m;
    map<int, int>st;
    vector<int>buff(n);
    bool flag = false;
    for (int i = 0; i < n; ++ i) {
        cin >> buff[i];
        st[buff[i]] ++;
    }

    sort(buff.begin(), buff.end());
    for (int i = 0; i < n; ++ i)
    {
        if (buff[i] * 2 == m) {
            if (st[buff[i]] >= 2) {
                cout << buff[i] << " " << m - buff[i] << endl;
                flag = true;
                break;
            }
        } else {
            if (st[m - buff[i]]) {
                cout << buff[i] << " " << m - buff[i] << endl;
                flag = true;
                break;
            }
        }
    }
    if (!flag) cout << "No Solution" << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

class Student {
public:
    int chinese,
        math,
        english,
        sum;
    int num;
    Student(){}
    Student(int chinese, int math, int english, int num)
    {
        this -> num = num;
        this -> chinese = chinese;
        this -> math = math;
        this -> english = english;
        this -> sum = math + english + chinese;

    }
    bool operator<(const Student& p) {
        if (p.sum != this-> sum)
            return p.sum < this -> sum;
        if(p.chinese != this -> chinese)
            return p.chinese < this -> chinese;
        if(p.num != this -> num)
            return p.num > this -> num;
    }
};

int main()
{
    int n; cin >> n;
    vector<Student>buff;
    for (int i = 0; i < n; ++ i)
    {
        int c, m, e; cin >> c >> m >> e;
        buff.push_back(Student(c, m, e, i + 1));
    }
    sort(buff.begin(), buff.end());
    for (int i = 0; i < 5; ++ i)
        cout << buff[i].num << " " << buff[i].sum << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string original, target;
    cin >> original >> target;

    int ans = 0;

    int len = target.length();
    for (int i = 0; i < len; ++ i)
    {
        int fro = i, beh;
        while (fro < len && target[fro] == original[fro]) fro ++;
        beh = fro + 1;
        while (beh < len && target[beh] == original[beh]) beh ++;
        if (beh < len && fro < len)
            ans += (beh - fro);
        i = beh;
    }

    cout << ans;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

char stable[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};

int main()
{
    int order; cin >> order;
    for (int i = 1; i <= 300; ++ i)
    {
        string buff = "", pre = "";
        int tmp = i * i;
        while (tmp)
        {
            buff += stable[tmp%order];
            tmp/=order;
        }
        int j = i;
        while (j)
        {
            pre += stable[j%order];
            j /= order;
        }
        if (buff == string(buff.rbegin(), buff.rend()))
            cout << string(pre.rbegin(), pre.rend()) << " " << buff << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int arr[N][N];

/*
    如果稍微苛刻一点，可以压缩一点空间
*/

int main()
{
    int n; cin >> n;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j <= i; ++ j)
            cin >> arr[i][j];


    for (int i = n - 2; i >= 0; -- i)
        for (int j = 0; j <= i; ++ j)
            arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1]);

    cout << arr[0][0];
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

// 中点就是指在中间的位置的点  而不是绝对的路径的中间
/*
    想了一下，如果一开始只有两个点，那么无所谓,当扩展到三个点就需要正好在中间的点，当四个点就是中间两个点的中间，这时候可能就已经不
    是绝对的中间位置了，而是点的中间
*/
int main()
{
    int n; cin >> n;
    vector<int>arr(n);    
    for (int i = 0; i < n; ++ i) cin >> arr[i];

    sort(arr.begin(), arr.end());
    int ans = 0;
    int dic = arr[n/2];
    for (int i = 0; i < n; ++ i)
    {
        ans += abs(dic - arr[i]);
    }
    cout << ans;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int arr[N], buff[N];

long long int ans = 0;

void merge_sort(int l, int r)
{
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int idx = 0, i = l, j = mid + 1;
    for (; i <= mid && j <= r;)
    {
        if (arr[i] <= arr[j]) buff[idx ++] = arr[i ++];
        else {
            buff[idx ++] = arr[j ++];
            ans += mid - i + 1;
        }
    }

    while (i <= mid) buff[idx ++] = arr[i ++];
    while (j <= r) buff[idx ++] = arr[j ++];

    idx = 0;
    for (int i = l; i <= r; ++ i)
    {
        arr[i] = buff[idx ++];
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++ i) cin >> arr[i];
    merge_sort(0, n - 1);
    cout << ans;
    return 0;
}