#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;

const int maxn=10010,MAXE=200100;
int ec;
int cc[2][maxn];
int vis[maxn];
int fir[maxn],nxt[MAXE],to[MAXE],cnt;
bitset<maxn> S;

void ae(int a,int b){ ++cnt; to[cnt]=b; nxt[cnt]=fir[a]; fir[a]=cnt; }
void dfs(int x,int col){
    vis[x]=1; ++cc[col][ec];
    for(int i=fir[x];i;i=nxt[i]){
        int id=to[i];
        if(!vis[id])dfs(id,col^1);
    }
}

void dit(){
    int n,m;scanf("%d%d",&n,&m); cnt=ec=0; S=0;
    for(int i=1;i<=n;++i)vis[i]=fir[i]=0;
    for(int i=0;i<m;++i){
        int a,b;scanf("%d%d",&a,&b);
        ae(a,b); ae(b,a);
    }
    for(int i=1;i<=n;++i){
        if(vis[i])continue;
        cc[0][ec]=cc[1][ec]=0;
        dfs(i,0); ++ec;
    }
    S[0]=1;
    for(int i=0;i<ec;++i){
        S=(S<<cc[0][i]) | (S<<cc[1][i]);
    }
    int ans=0;
    for(int i=0;i<=n;++i){
        if(S[i]){
            int v=i*(n-i)-m;
            if(v>ans)ans=v;
        }
    }
    printf("%d\n",ans);
}

int main() {
    int t;scanf("%d",&t);
    while(t--)dit();
}