#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=2e5+10,M=N*2;
int T,n,m,q,k;
vector<int>A[N],B[M];
int dft,top,dfn[N],low[N],stk[N];
void add(int u,int v){
	// debug(u,v);
	B[u].push_back(v),B[v].push_back(u);
}
void tarjan(int u,int fa=0){
	dfn[u]=low[u]=++dft,stk[++top]=u;
	for(int v:A[u])if(v^fa){
		if(!dfn[v]){
			tarjan(v),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				add(++k,u);
				do add(k,stk[top]);while(stk[top--]^v);
			}
		}else low[u]=min(low[u],dfn[v]);
	}
}
int sum[M],fa[M],dep[M];
namespace Path{
	int dft,siz[M],son[M],top[M],dfn[M],pos[M];
	void dfs1(int u){
		son[u]=0,siz[u]=1,dep[u]=dep[fa[u]]+1;
		sum[u]=0;
		for(int v:B[u])if(v^fa[u]){
			fa[v]=u,dfs1(v);
			siz[u]+=siz[v],sum[u]+=sum[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
		if(u<=n)sum[u]++;
	}
	void dfs2(int u,int t){
		top[u]=t,pos[dfn[u]=++dft]=u;
		if(son[u])dfs2(son[u],t);
		for(int v:B[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
	}
	int LCA(int u,int v){
		for(;top[u]^top[v];u=fa[top[u]]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
		}
		return dep[u]<dep[v]?u:v;
	}
	int jump(int u,int k){
		for(;k>dep[u]-dep[top[u]];u=fa[top[u]])k-=dep[u]-dep[top[u]]+1;
		return pos[dfn[u]-k];
	}
}
void get(){
	scanf("%d%d",&n,&m),k=n;
	for(int u,v;m--;){
		scanf("%d%d",&u,&v);
		A[u].push_back(v),A[v].push_back(u);
	}
	tarjan(1);
	Path::dfs1(1),Path::dfs2(1,1);
	scanf("%d",&q);
	for(int u,v;q--;){
		scanf("%d%d",&u,&v);
		int t=Path::LCA(u,v);
		if(v==t)swap(u,v);
		if(u==t){
			printf("%d\n",sum[Path::jump(v,dep[v]-dep[u]-1)]-sum[v]+2);
		}else{
			printf("%d\n",n-sum[u]-sum[v]+2);
		}
	}
}
void clr(){
	dft=top=Path::dft=0;
	for(int i=1;i<=n;i++){
		A[i].clear();
		dfn[i]=low[i]=0;
	}
	for(int i=1;i<=k;i++){
		B[i].clear();
	}
}
int main(){
	for(scanf("%d",&T);T--;clr())get();
	return 0;
}