#include<bits/stdc++.h>//60 #define int long long using namespace std; const int N=100010; int n,m,ans; int b[N],res; struct node{ int x1,y1,x2,y2; }p[N]; bool cmp(node x,node y) { return x.y1<y.y1; } void dfs(int x,int now) { if(x==m+1) { ans=max(ans,res); return ; } for(int i=0;i<m;i++) { if(((1<<i)&now)==0) { int x1=p[i+1].x1,y1=p[i+1].y1,x2=p[i+1].x2,y2=p[i+1].y2; int lst1=b[x1],lst2=b[x2],lstres=res; res+=y1-b[x1]+y2-b[x2]; b[x1]=y1,b[x2]=y2; dfs(x+1,now|(1<<i)); b[x1]=lst1,b[x2]=lst2,res=lstres; } } } void solve() { cin>>n>>m; for(int i=1;i<=n;i++) b[i]=0; if(m<=10) { for(int i=1;i<=m;i++) cin>>p[i].x1>>p[i].y1>>p[i].x2>>p[i].y2; res=0,ans=0; dfs(1,0); cout<<ans<<'\n'; return ; } bool specialA=1; for(int i=1;i<=m;i++) { cin>>p[i].x1>>p[i].y1>>p[i].x2>>p[i].y2; if(p[i].y1!=p[i].y2) specialA=0; } if(specialA) { sort(p+1,p+m+1,cmp); for(int i=1;i<=m;i++) { int x1=p[i].x1,y1=p[i].y1,x2=p[i].x2,y2=p[i].y2; b[x1]=y1,b[x2]=y2; } int nowans=0; for(int i=1;i<=n;i++) nowans+=b[i]; cout<<nowans<<'\n'; return ; } for(int i=1;i<=m;i++) { int x1=p[i].x1,y1=p[i].y1,x2=p[i].x2,y2=p[i].y2; b[x1]=max(b[x1],y1); b[x2]=max(b[x2],y2); } int ans=0; for(int i=1;i<=n;i++) ans+=b[i]; cout<<ans<<'\n'; } signed main() { //freopen("max.in","r",stdin); //freopen("max.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T; cin>>T; while(T--) solve(); return 0; }