#include <bits/stdc++.h>

using namespace std;

vector<int> match, vis;
vector<vector<int>> AdjList;

int Aug(int L) {
  if (vis[L]) return 0;
  vis[L] = 1;
  for (int j = 0; j < (int)AdjList[L].size(); j++) {
    int r = AdjList[L][j];
    if (match[r] == -1) {
      match[r] = L; return 1;
    }
  }
  for (int j = 0; j < (int)AdjList[L].size(); j++) {
    int r = AdjList[L][j];
    if (Aug(match[r])) {
      match[r] = L; return 1;
    }
  }
  return 0;
}

int tc, n, m;
int grid[200][200];
int wallsabove[200][200];
int main() {
  scanf("%d", &tc);
  while (tc--) {
    //memset(grid, 0, sizeof(grid));
    //memset(wallsabove, 0, sizeof(wallsabove));
    AdjList.clear();
    match.clear();
    vis.clear();
    vector<int> rowsplits;
    vector<int> colsplits;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
      colsplits.push_back(1);
    }
    for (int i = 0; i < n; i++) {
      int rCount = 1;
      for (int j = 0; j < m; j++) {
        scanf("%d", &grid[i][j]);
        if (grid[i][j] == 2) {
          if (j != 0 && grid[i][j-1] != 2) {
            rCount++;
          }
          if (i == 0 || grid[i-1][j] == 2) {
            wallsabove[i][j] = i == 0? 0 : wallsabove[i-1][j];
          } else {
            colsplits[j]++;
            wallsabove[i][j] = i == 0? 1 : wallsabove[i-1][j] + 1;
          }
        } else {
          wallsabove[i][j] = i == 0? 0 : wallsabove[i-1][j];
        }
      }
      rowsplits.push_back(rCount);
      if (i != 0) {
        rowsplits[i] += rowsplits[i-1];
      }
    }
    for (int i = 0; i < rowsplits[n-1]; i++) {
      vector<int> tmp;
      AdjList.push_back(tmp);
    }
    // Aggregate
    for (int i = 1; i < m; i++) {
      colsplits[i] += colsplits[i-1];
    }

    for (int i = 0; i < n; i++) {
      int prevRowsNodes = i == 0? 0 : rowsplits[i-1];
      int walls = 0;
      for (int j = 0; j < m; j++) {
        if (grid[i][j] == 2) {
          if (j != 0 & grid[i][j-1] != 2) walls++;
        } else if (grid[i][j] == 1) {
          continue;
        } else {
          int thisRNode = prevRowsNodes + walls;
          int prevCNodes = j == 0? 0 : colsplits[j-1];
          int wallsabv = wallsabove[i][j];
          int thisCNode = rowsplits[n-1] + wallsabv + prevCNodes;
          AdjList[thisRNode].push_back(thisCNode);
          //printf("%d to %d\n", thisRNode, thisCNode);
        }
      }
    }
    int MCBM = 0;
    match.assign(rowsplits[n-1]+colsplits[m-1],-1);
    for (int L = 0; L < rowsplits[n-1]; L++) {
      vis.assign(rowsplits[n-1],0);
      MCBM += Aug(L);
    }
    printf("%d\n", MCBM);
  }
  return 0;
}