## STOKROTKI ##

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t-- > 0) {
        int w, k;
        cin>> w >> k;
        int a[w][k];
        for (int i = 0; i < w; i++)
        for (int j = 0; j < k; j++)
        cin >> a[i][j];
            ;
     int c[w][k];
     c[0][0] = a[0][0];
     for (int i = 1; i < w; i++)
     c[i][0] = a[i][0] + c[i-1][0];
     for (int j = 1; j < k; j++)
     c[0][j] = a[0][j] + c[0][j-1];
      for (int i = 1; i < w; i++)
         for (int j = 1; j < k; j++)
         c[i][j] = a[i][j] + max(c[i-1][j], c[i][j-1]);
        ;

      cout << c[w-1][k-1] << endl;


    }


    return 0;
}


## NAJDLUZSZA WYMAZANKA

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <limits>

#define DEBUG 0


class LCS
{
  std::string u;
  std::string v;

  std::vector<std::vector<unsigned short> > lengths;

  bool need_predecessors;

  enum direction
  {
    NONE,
    UP,
    LEFT,
    DIAGONAL
  };

  std::vector<std::vector<direction> > directions;

  void init()
  {
    lengths.resize(u.length() + 1);

    lengths[0].resize(v.length() + 1, 0);

    for(std::vector<std::vector<unsigned short> >::iterator it = lengths.begin() + 1; it != lengths.end(); ++it)
    {
      it->resize(v.length() + 1);
      (*it)[0] = 0;
    }

    if (need_predecessors)
    {
      directions.resize(u.length() + 1);
      for(std::vector<std::vector<direction> >::iterator it = directions.begin(); it != directions.end(); ++it)
      {
        it->resize(v.length() + 1);
      }

      for (unsigned short i = 0; i <= u.length(); ++i)
      {
        directions[i][0] = NONE;
      }
      for (unsigned short i = 1; i <= v.length(); ++i)
      {
        directions[0][i] = NONE;
      }
    }
  }

  void set_length_and_path_from_predecessors(const unsigned short col, const unsigned short row)
  {
    const char letter_u = u[col - 1];
    const char letter_v = v[row - 1];

    if (letter_u == letter_v)
    {
      if (need_predecessors) directions[col][row] = DIAGONAL;
      lengths[col][row] = 1 + lengths[col - 1][row - 1];
    }
    else if (lengths[col][row - 1] >= lengths[col - 1][row])
    {
      if (need_predecessors) directions[col][row] = UP;
      lengths[col][row] = lengths[col][row - 1];
    }
    else
    {
      if (need_predecessors) directions[col][row] = LEFT;
      lengths[col][row] = lengths[col - 1][row];
    }
  }

public:
  enum str_id
  {
    U,
    V
  };

  void read_line(str_id s)
  {
    switch (s)
    {
      case U:
        std::cin >> u;
        break;

      case V:
        std::cin >> v;
        break;
    }
  }


  void run(bool predecessors = true)
  {
    need_predecessors = predecessors;
    init();

    for (unsigned short row = 1; row <= v.length(); ++row)
    {
      for (unsigned short col = 1; col <= u.length(); ++col)
      {
        set_length_and_path_from_predecessors(col, row);
      }
    }

  }


  unsigned short longest_length()
  {
    return lengths[u.length()][v.length()];
  }

  void clear()
  {
    u.clear();
    v.clear();
    lengths.resize(0);
    directions.resize(0);
  }

  std::string longest_common_subsequence()
  {
    std::vector<char> s_vec;
    s_vec.resize(longest_length());

    int x = u.length();
    int y = v.length();

    int i = longest_length() - 1;

    while (i >= 0)
    {
      switch (directions[x][y])
      {
        case UP:
          --y;
          break;

        case LEFT:
          --x;
          break;

        default:
          s_vec[i] = u[x-1];
          --i;
          --x;
          --y;
          break;
      }
    }

    return std::string(s_vec.begin(), s_vec.end());
  }

  void DEBUG_print_strings()
  {
    if (DEBUG)
    {
      std::cout << "PRINTING STRINGS" << std::endl
                << "U.len=" << u.length() << " with " << u << std::endl
                << "V.len=" << v.length() << " with " << v << std::endl;
    }
  }

  void DEBUG_print_lengths_contents()
  {
    if (DEBUG)
    {
      std::cout << "PRINT LENGTHS CONTENTS:" << std::endl;
      for (unsigned short it_v = 0; it_v <= v.length(); ++it_v)
      {
        for (unsigned short it_u = 0; it_u <= u.length(); ++it_u)
        {
          std::cout << lengths[it_u][it_v] << "\t";
        }
        std::cout << std::endl;
      }
    }
  }

  void DEBUG_print_directions_contents()
  {
    if (DEBUG)
    {
      std::cout << "PRINT DIRECTIONS CONTENTS:" << std::endl;
      for (unsigned short it_v = 0; it_v <= v.length(); ++it_v)
      {
        for (unsigned short it_u = 0; it_u <= u.length(); ++it_u)
        {
          char c = ' ';
          switch(directions[it_u][it_v])
          {
            case NONE:
              c = ' ';
              break;

            case UP:
              c = '^';
              break;

            case LEFT:
              c = '<';
              break;

            case DIAGONAL:
              c = '\\';
              break;
          }
          std::cout << c << "\t";
        }
        std::cout << std::endl;
      }
    }
  }
};


void omg_just_ignore_this_number_and_go_on()
{
  unsigned short x;
  std::cin >> x;
  //std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  //std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

int main()
{
  std::ios_base::sync_with_stdio(false);

  LCS lcs;

  lcs.read_line(LCS::U);
  lcs.read_line(LCS::V);

  lcs.DEBUG_print_strings();

  lcs.run();

  lcs.DEBUG_print_lengths_contents();
  lcs.DEBUG_print_directions_contents();

  std::cout << lcs.longest_common_subsequence() << std::endl;

  return 0;
}

## PODCIAG

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s1,s2,sLCS;
  int ** L,i,j,m,n;

  getline(cin,s1);
  getline(cin,s2);

  m  = s1.length();
  n  = s2.length();



  L = new int * [m + 1];
  for(i = 0; i <= m; i++) L[i] = new int[n + 1];



  for(i = 0; i <= m; i++) L[i][0] = 0;
  for(j = 0; j <= n; j++) L[0][j] = 0;
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
      if(s1[i] == s2[j])
        L[i + 1][j + 1] = 1 + L[i][j];
      else
        L[i + 1][j + 1] = max(L[i + 1][j],L[i][j + 1]);



  sLCS = ""; i = m - 1; j = n - 1;
  while((i >= 0) && (j >= 0))
    if(s1[i] == s2[j])
    {
      sLCS = s1[i] + sLCS;
      i--; j--;
    }
    else if(L[i + 1][j] > L[i][j + 1]) j--;
    else i--;
  cout << L[m][n] << endl;
  return 0;
}