#include<bits/stdc++.h>
using namespace std;
const int maxd=18;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<vector<int>> G(n+5),tG(n+n+5);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int ind;
		vector<int> dfn(n+5),low(n+5),ins(n+5);
		stack<int> s;
		int bcnt=0;
		function<void(int,int)> dfs1=[&](int u,int p)
		{
			dfn[u]=low[u]=++ind;
			s.push(u);ins[u]=1;
			for(auto v:G[u])
			{
				if(v==p)continue;
				if(not ins[v])
				{
					dfs1(v,u);
					low[u]=min(low[u],low[v]);
					if(low[v]>=dfn[u])
					{
						++bcnt;
						int vv;
						do
						{
							vv=s.top();
//							cerr<<"addedge "<<vv<<' '<<bcnt+n<<endl;
							tG[bcnt+n].push_back(vv);
							tG[vv].push_back(bcnt+n);
							ins[vv]=2;
							s.pop();
						}
						while(v!=vv);
//						cerr<<"addedge "<<u<<' '<<bcnt+n<<endl;
						tG[bcnt+n].push_back(u);
						tG[u].push_back(bcnt+n);
					}
				}
				else if(ins[v]==1)
				{
					low[u]=min(low[u],dfn[v]);
				}
			}
			if(not p)s.pop();
		};
		dfs1(1,0);
		vector<int> w(n+bcnt+5);
		for(int i=1;i<=n;i++)w[i]=-1;
		for(int i=n+1;i<=n+bcnt;i++)w[i]=tG[i].size();
		vector<int> len(n+bcnt+5),dep(n+bcnt+5),pa(n+bcnt+5);
		function<void(int)> dfs2=[&](int u)
		{
			for(auto v:tG[u])
			{
				if(not dep[v])
				{
					dep[v]=dep[u]+1;
					len[v]=len[u]+w[v];
					pa[v]=u;
					dfs2(v);
				}
			}
		};
		len[1]=w[1];
		dep[1]=1;
		dfs2(1);
		vector<vector<int>> jmp(maxd+5,vector<int>(n+bcnt+5));
		for(int i=1;i<=n+bcnt;i++)
			jmp[0][i]=pa[i];
		for(int d=1;d<=maxd;d++)
			for(int i=1;i<=n+bcnt;i++)
				jmp[d][i]=jmp[d-1][jmp[d-1][i]];
		auto getlca=[&](int u,int v)
		{
			if(dep[v]<dep[u])swap(u,v);
			for(int d=maxd;d>=0;d--)
				if(dep[jmp[d][v]]>=dep[u])
					v=jmp[d][v];
			if(u==v)return u;
			for(int d=maxd;d>=0;d--)
				if(jmp[d][u]!=jmp[d][v])
					u=jmp[d][u],v=jmp[d][v];
			return pa[u];
		};
//		for(int i=1;i<=n+bcnt;i++)cerr<<i<<' '<<w[i]<<' '<<len[i]<<endl;
		int q;
		cin>>q;
		while(q--)
		{
			int u,v;
			cin>>u>>v;
			int lca=getlca(u,v);
//			cerr<<"lca "<<lca<<endl;
			cout<<2+len[u]+len[v]-len[lca]-len[pa[lca]]<<"\n";
		}
	}
	return 0;
}