#include<map>
#include<set>
#include<ctime>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define lb long double
#define UI unsigned int
//#define mod 1000000007
#define mod (1LL<<32)
#define inf 1000000000
#define N 100000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,n,m;
int a[1005][1005],L[1005][1005],R[1005][1005],U[1005][1005],D[1005][1005];
pair<int,int>t[1005];
void getans()
{
    UI ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            ll l=j-L[i][j],r=R[i][j]-j,u=i-U[i][j],d=D[i][j]-i;
//            cout<<i<<' '<<j<<' '<<l<<' '<<r<<' '<<u<<' '<<d<<endl;
            ll t=l*r*u*d*(l+r)*(u+d)/4;
            ans+=a[i][j]*t%mod;       
        }
    cout<<ans<<endl;
}
int main()
{
    T=read();
    while(T--)
    {
        n=read();m=read();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=read();
        stack<int>st;
        for(int i=1;i<=n;i++)
        {            
            a[i][0]=a[i][m+1]=-inf;
            while(!st.empty())st.pop();st.push(0);
            for(int j=1;j<=m;j++)
            {
                while(!st.empty()&&a[i][st.top()]>a[i][j])st.pop();
                L[i][j]=st.top();
                st.push(j);
            }
            while(!st.empty())st.pop();st.push(m+1);
            for(int j=m;j>=1;j--)
            {
                while(!st.empty()&&a[i][st.top()]>a[i][j])st.pop();
                R[i][j]=st.top();
                st.push(j);
            }
        }
        for(int i=1;i<=m;i++)
        {
            a[0][i]=a[n+1][i]=inf;
            while(!st.empty())st.pop();st.push(0);
            for(int j=1;j<=n;j++)
            {
                while(!st.empty()&&a[st.top()][i]<a[j][i])st.pop();
                U[j][i]=st.top();
                st.push(j);
            }
            while(!st.empty())st.pop();st.push(n+1);
            for(int j=n;j>=1;j--)
            {
                while(!st.empty()&&a[st.top()][i]<a[j][i])st.pop();
                D[j][i]=st.top();
                st.push(j);
            }            
        }
        getans();
    }
    return 0;
}