#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 s1[M],s2[M],fa[M];
namespace Path{
	int siz[M],son[M],top[M],dep[M];
	void dfs1(int u){
		son[u]=0,siz[u]=1,dep[u]=dep[fa[u]]+1;
		s1[u]=s1[fa[u]],s2[u]=s2[fa[u]];
		if(u<=n)s1[u]++;
		else s2[u]+=B[u].size();
		for(int v:B[u])if(v^fa[u]){
			fa[v]=u,dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void dfs2(int u,int t){
		top[u]=t;
		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;
	}
}
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);
		#define calc(x) (s##x[u]+s##x[v]-s##x[t]-s##x[fa[t]])
		// debug(calc(2),calc(1),u,v,t);
		printf("%d\n",calc(2)-calc(1)+2);
	}
}
void clr(){
	dft=top=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;
}