#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}

const int MaxN = 100005;
const int MaxM = 200005;
namespace queue{
int q[MaxN<<1];
typedef int* iterator;
iterator begin(){ return q; }
}
namespace Graph{
struct Edge{
int to, nxt; Edge(){}
Edge(int T,int N){
to = T, nxt = N;
}
};
Edge e[MaxM<<2];
int cntEdge, head[MaxN<<1];
void addEdge(int a,int b){
e[cntEdge] = Edge(b,head[a]);
head[a] = cntEdge ++;
e[cntEdge] = Edge(a,head[b]);
head[b] = cntEdge ++;
}
int dep[MaxN<<1];
void input(int n,int m){
for(int i=1; i<=2*n; ++i)
dep[i] = head[i] = -1;
cntEdge = 0; // several cases
for(int i=1,a,b; i<=m; ++i){
a = readint(), b = readint();
addEdge(a,b+n), addEdge(a+n,b);
}
}
void scan(){
queueiterator fro = queuebegin();
queueiterator bac = queuebegin();
*(bac ++) = 1; dep[1] = 0;
for(; fro!=bac; ++fro)
for(int i=head[*fro]; ~i; i=e[i].nxt)
if(dep[e[i].to] == -1){
dep[e[i].to] = dep[*fro]+1;
*(bac ++) = e[i].to;
}
}
}

int n, m;
void input(){
n = readint(), m = readint();
Graphinput(n,m), Graphscan();
}

int ans;

define DDQ vector<PII>::iterator

int eliminateChain(const DDQ &bg,const DDQ &ed){
int used = 0;
for(DDQ i=ed; i!=bg; --i){
used = min(i->second-used,(i-1)->second);
ans += used;
}
return bg->second-used;
}

undef DDQ

bool vis[MaxN<<1];
vector<int> tree[MaxN<<1];
vector<PII> len_cnt;
vector<int> trash;
int getOnion(){
using Graph::dep;
int tot = 0;
for(int i=1; i<=n; ++i){
int l = dep[i], r = dep[i+n];
if(l > r) swap(l,r);
if(l != -1)
tree[l+r].push_back(r-l+1);
tot += (l != -1) + (r != -1);
}
ans = 0;
trash.clear();
memset(vis+1,0,n<<1);
for(int i=1; i<=2*n; i+=2){
len_cnt.clear();
vector<int> &v = tree[i];
sort(v.begin(),v.end());
int len = v.size();
for(int p=0,j=p; p!=len; p=j){
while(j != len && v[j] == v[p])
++ j;
len_cnt.push_back(make_pair(v[p],j-p));
len_cnt.push_back(make_pair(v[p],j-p));
}
len = len_cnt.size();
for(int p=0,j=p; p!=len; p=++j){
while(j+1 != len)
if(j&1){
if(len_cnt[j+1].first == len_cnt[j].first+2)
++ j; else break;
}
else{
if(vis[len_cnt[j].first])
++ j; else break;
}
int rest = eliminateChain(len_cnt.begin()+p,len_cnt.begin()+j);
if(!p && len_cnt[0].first == 2)
ans += (rest>>1);
}
while(!trash.empty()){
vis[trash.back()] = false;
trash.pop_back();
}
while(!len_cnt.empty()){
trash.push_back(len_cnt.back().first);
len_cnt.pop_back();
vis[trash.back()] = true;
}
}
return tot-1-ans;
}

void solve(){
for(int i=1; i<=2*n; i+=2)
tree[i].clear();
printf("%d\n",getOnion());
}

int main(){
for(int T=readint(); T; --T)
input(), solve();
return 0;
}