#include<bits/stdc++.h>
using namespace std;

int dp[205][205][2];
int arr[205][205];

int solve(int i, int j, int d, int m, int n) {
    if(i<0 i>=m j<0 j>=n arr[i][j]==-1) return 0;
    if(dp[i][j][d] != -1) return dp[i][j][d];
    int res = arr[i][j];
    if(d == 0) {
        res += max(solve(i, j+1, d, m, n), solve(i+1, j, 1-d, m, n));
    } else {
        res += max(solve(i, j-1, d, m, n), solve(i+1, j, 1-d, m, n));
    }
    dp[i][j][d] = res;
    return res;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int m, n;
        cin >> m >> n;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                char c;
                cin >> c;
                if(c == '1') arr[i][j] = 1;
                else if(c == '0') arr[i][j] = 0;
                else arr[i][j] = -1;
            }
        }
        memset(dp, -1, sizeof(dp));
        cout << max(solve(0, 0, 0, m, n), arr[0][0] + solve(0, 0, 1, m, n)) << endl;
    }
    return 0;
}

Compro ✅