#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<bitset>
using namespace std;
#define ll long long 
#define N 110000
bitset<11000>ans;
int s[N][2],fa[N],n,m,a[N];
ll read(){
   char ch=getchar(),last=' ';
   while(ch<'0' || ch>'9')last=ch,ch=getchar();
   ll ans=0;
   while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
   if(last=='-')ans=-ans;
   return ans;
}
int find(int x){
    if(x==fa[x])return x;
    int t=fa[x];
    fa[x]=find(fa[x]);
    a[x]=a[x]^a[t];
    return fa[x];
}
void solved(){
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)fa[i]=i,s[i][0]=0,s[i][1]=0,a[i]=0;
     for(int i=1;i<=m;i++){
             int x=read(),y=read();
             int fx=find(x),fy=find(y);
             if(fx==fy)continue;
             fa[fx]=fy;
             a[fx]=1^a[x]^a[y];
     }
     for(int i=1;i<=n;i++)ans[i]=0;
     ans[0]=1;
     for(int i=1;i<=n;i++)s[find(i)][a[i]]++;
     for(int i=1;i<=n;i++)
     if(fa[i]==i){
     //  cout<<s[i][0]<<" "<<s[i][1]<<endl; 
       ans|=(ans<<s[i][0])|(ans<<s[i][1]);
       }
     int Max=0;
     for(int i=0;i<=n;i++)
     if(ans[i])Max=max(Max,i*(n-i)-m);
     printf("%d\n",Max);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solved();
    return 0;
}