Greek Traveller(GS 2nd question)

// Pratiyush Mishra

#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long int
#define LL_MAX 9223372036854775807
#define pb push_back
#define pf push_front
#define mp make_pair
#define popb pop_back
#define vl vector<ll>
#define pl pair<ll,ll>
#define bs(v, x) binary_search(v.begin(), v.end(), x)
#define mem1(a) memset(a, -1, sizeof(a))
#define popf pop_front
#define p0(x) cout << x << " "
#define p1(x) cout << x << '\n'
#define p2(x, y) cout << x << " " << y << '\n'
#define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
#define printv(v)                   \
  for (ll i = 0; i < v.size(); ++i) \
    cout << v[i] << " ";            \
  cout << '\n'
#define pr1(x) cout << fixed << setprecision(15) << x << '\n'
#define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
#define mod 1000000007
#define mod1 998244353
#define fio                         \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)
#define get(n) \
  ll n;        \
  cin >> n
#define getvec(v, n)         \
  vector<ll> v(n);           \
  for (ll i = 0; i < n; i++) \
    cin >> v[i];
#define getstr(s) \
  string s;       \
  cin >> s
#define all(x) x.begin(), x.end()
#define countBits(x) __builtin_popcount(x)
using namespace std;

int find(vector<int> &tree, int x)
{
    if (tree[x] == x)
        return x;
    return tree[x] = find(tree, tree[x]);
}

void join(vector<int> &tree, int a, int b)
{
    int x = find(tree, a);
    int y = find(tree, b);
    if (x == y)
        return;
    tree[x] = y;
}

void mainSolve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            if (x == 0)
                continue;
            ans += x;
            v.push_back({i, j, x});
        }
    }
    vector<pair<int, pair<int, int>>> edges;
    n = v.size();
    vector<int> tree(n);
    for (int i = 0; i < n; i++)
        tree[i] = i;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            vector<int> a = v[i];
            vector<int> b = v[j];
            int e = 2 * (abs(a[0] - b[0]) + abs(a[1] - b[1]));
            edges.push_back({e, {i, j}});
        }
    }
    sort(edges.begin(), edges.end());
    for (auto it : edges)
    {
        int e = it.first;
        int i = it.second.first;
        int j = it.second.second;
        int x = find(tree, i);
        int y = find(tree, j);
        if (x == y)
            continue;
        join(tree, x, y);
        ans += e;
    }
    ans = (ans + 7) / 8;
    p1(ans);
}

int main()
{
    fio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    get(t);
    //ll t = 1;
    while (t--)
    {
        mainSolve();
    }
    return 0;
}