#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<utility>
#define ll long long
#define max 747474747LL
using namespace std;
ll arr[7000][6];
struct edge{
int cost ;
int a,b;
}list[30000000];
bool cmp(edge a,edge b)
{
return a.cost>b.cost;
}
int find(int *p,int x)
{
if(p[x]==x)return x;
return p[x]=find(p,p[x]);
}
void join(int *p,int a,int b)
{
p[find(p,a)]=find(p,b);
}
int sqr(int n)
{
ll x=(ll)n*n;
return (int)(x%max);
}
int calc(int a,int b,int d)
{
int i;
ll ans=0LL;
for(i=0;i<d;i++)
{
ans=ans+sqr(arr[a][i]-arr[b][i]);
}
return (int)(ans%max);
}
int kruskal(int n,int d)
{
int i,j,k,p[7000];
ll cost;
for(i=0;i<n;i++)
p[i]=i;
for(i=k=0;i<n;i++)
for(j=i+1;j<n;j++)
list[k].a=i, list[k].b=j, list[k++].cost=calc(i,j,d);
sort(list,list+k,cmp);
for(cost=1LL,i=0;i<k;i++)
if(find(p,list[i].a)!=find(p,list[i].b))
{
if(list[i].cost<2)break;
join(p,list[i].a,list[i].b);
cost=(cost*list[i].cost)%max;
}
/*for(i=0;i<n;i++)
find(p,i);*/
return (int)cost;
}
int main()
{
int t,n,d,i,j,k;
int ans,x;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&d);
for(i=0;i<n;i++)
for(j=0;j<d;j++)
scanf("%d",&arr[i][j]);
ans=kruskal(n,d);
printf("%d\n",ans);
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8c3RhY2s+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxzZXQ+CiNpbmNsdWRlPHV0aWxpdHk+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbWF4IDc0NzQ3NDc0N0xMCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxsIGFycls3MDAwXVs2XTsKc3RydWN0IGVkZ2V7CiAgICAgICBpbnQgY29zdCA7CiAgICAgICBpbnQgYSxiOwogICAgICAgfWxpc3RbMzAwMDAwMDBdOwoKYm9vbCBjbXAoZWRnZSBhLGVkZ2UgYikKewogICAgIHJldHVybiBhLmNvc3Q+Yi5jb3N0OwogfQoKaW50IGZpbmQoaW50ICpwLGludCB4KQp7CiAgICBpZihwW3hdPT14KXJldHVybiB4OwogICAgcmV0dXJuIHBbeF09ZmluZChwLHBbeF0pOwp9Cgp2b2lkIGpvaW4oaW50ICpwLGludCBhLGludCBiKQp7CiAgICAgcFtmaW5kKHAsYSldPWZpbmQocCxiKTsKIH0KCmludCBzcXIoaW50IG4pCnsKICAgIGxsIHg9KGxsKW4qbjsKICAgIHJldHVybiAoaW50KSh4JW1heCk7Cn0KCmludCBjYWxjKGludCBhLGludCBiLGludCBkKQp7CiAgICBpbnQgaTsKICAgIGxsIGFucz0wTEw7CgogICAgZm9yKGk9MDtpPGQ7aSsrKQogICAgewogICAgICAgIGFucz1hbnMrc3FyKGFyclthXVtpXS1hcnJbYl1baV0pOwogICAgfQogICAgcmV0dXJuIChpbnQpKGFucyVtYXgpOwp9CgoKaW50IGtydXNrYWwoaW50IG4saW50IGQpCnsKICAgIGludCBpLGosayxwWzcwMDBdOwogICAgbGwgY29zdDsKCiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICBwW2ldPWk7CgoKICAgIGZvcihpPWs9MDtpPG47aSsrKQogICAgZm9yKGo9aSsxO2o8bjtqKyspCiAgICBsaXN0W2tdLmE9aSwgbGlzdFtrXS5iPWosIGxpc3RbaysrXS5jb3N0PWNhbGMoaSxqLGQpOwoKICAgIHNvcnQobGlzdCxsaXN0K2ssY21wKTsKCiAgICBmb3IoY29zdD0xTEwsaT0wO2k8aztpKyspCiAgICBpZihmaW5kKHAsbGlzdFtpXS5hKSE9ZmluZChwLGxpc3RbaV0uYikpCiAgICB7CiAgICBpZihsaXN0W2ldLmNvc3Q8MilicmVhazsKICAgIGpvaW4ocCxsaXN0W2ldLmEsbGlzdFtpXS5iKTsKICAgIGNvc3Q9KGNvc3QqbGlzdFtpXS5jb3N0KSVtYXg7CiAgICB9CgogICAgLypmb3IoaT0wO2k8bjtpKyspCiAgICBmaW5kKHAsaSk7Ki8KCiAgICByZXR1cm4gKGludCljb3N0Owp9CgoKaW50IG1haW4oKQp7CiAgICBpbnQgdCxuLGQsaSxqLGs7CiAgICBpbnQgYW5zLHg7CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBzY2FuZigiJWQgJWQiLCZuLCZkKTsKCiAgICAgICAgZm9yKGk9MDtpPG47aSsrKQogICAgICAgIGZvcihqPTA7ajxkO2orKykKICAgICAgICBzY2FuZigiJWQiLCZhcnJbaV1bal0pOwoKCiAgICAgICAgYW5zPWtydXNrYWwobixkKTsKICAgICAgICBwcmludGYoIiVkXG4iLGFucyk7CiAgICB9CnJldHVybiAwOwp9Cg==