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

#define int long long
#define endl '\n'
using ll = long long;

const int N = 1e3 + 5;

int n, m;
int a[N][N];
int dis[N][N];
bool vis[N][N];

int dx[2] = {2, 1};
int dy[2] = {0, 1};

struct str {
    int x, y;
    int d;
    bool operator < (const str & tmp) const {
        return d > tmp.d;
    }
};

void bfs () {
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            dis[i][j] = 1e8;
            vis[i][j] = 0;
        }
    }
    priority_queue<str> q;
    q.push({0, 0, 0});
    dis[0][0] = 0;
    while (!q.empty()) {
        int x = q.top().x, y = q.top().y;
        q.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
//      cout << x << ',' << y << "  " << dis[x][y] << endl;
        for (int i = 0; i < 2; i ++) {
            int nx = (x + dx[i]) % n;
            int ny = y + dy[i];
//          cout << nx << ' ' << ny << endl;
            if (vis[nx][ny] || ny >= m || a[nx][ny]) continue;
            if (i == 0 && a[(x + 1) % n][ny]) continue;
            if (dis[x][y] + 1 < dis[nx][ny]) {
                dis[nx][ny] = dis[x][y] + 1;
                q.push({nx, ny, dis[nx][ny]});
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cin >> a[i][j];
        }
    }
    bfs();
    int ans = 1e8;
    for (int i = 0; i < n; i ++) {
        if (dis[i][m - 1] >= ans) continue;
        int tmp = (i + n - dis[i][m - 1] % n) % n;
        ans = min(ans, dis[i][m - 1] + min(n - 1 - tmp, tmp + 1));
//      cout << i << ' ' << dis[i][m - 1] << "  " << tmp << endl;
    }
    if (ans == 1e8) cout << -1 << endl;
    else cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}