#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+7;
int n,m,q;
vector<int>vv[N];
int head[N],cnt;
struct E{
    int nex, to;
    E(int a=-1, int b=0):nex(a), to(b) {}
}edge[1000005];
void add(int u, int v)
{
    edge[cnt]=E(head[u], v);
    head[u]=cnt++;
}
int dfn[N],tot,low[N],Stap[N],Stop,Bcnt,cut[N];
void Tarjan(int u,int fa,int rt){
    dfn[u]=low[u]=++tot;
    Stap[++Stop]=u;
    int cntzs=0;
    for(int i=head[u],v,p;~i;i=edge[i].nex){
        v=edge[i].to;
        if(v==fa)continue;
        if(!dfn[v]){
            Tarjan(v,u,i);
            cntzs++;
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                if(u!=rt)cut[u]=1;
                Bcnt++;
                vv[Bcnt+n].clear();
                do
                {
                    p=Stap[Stop--];
                    vv[n+Bcnt].push_back(p);
                    vv[p].push_back(n+Bcnt);
                } while(p^v);
                vv[n+Bcnt].push_back(u);
                vv[u].push_back(n+Bcnt);
            }
        }
        else low[u]=min(low[u],dfn[v]);
        if(rt==u&&cntzs>1)cut[u]=1;
    }
}
int siz[N],son[N],dep[N],fa[N];
void dfs(int u,int pre)
{
    dep[u]=dep[pre]+1;
    if(u<=n)siz[u]=1;
    else siz[u]=0;
    fa[u]=pre;
    for(auto v:vv[u])if(v!=pre){
        dfs(v,u);
        if(siz[v]>siz[son[u]])son[u] = v;
        siz[u]+=siz[v];
    }
}
int top[N],id[N],icnt,cid[N];
void dfs2(int u,int tp)
{
    top[u]=tp;
    id[u]=++icnt;
    cid[icnt]=u;
    if(son[u])dfs2(son[u],tp);
    for(auto v:vv[u])if(v!=fa[u]&&v!=son[u]){
        dfs2(v,v);
    }
}
int lca(int a,int b){
    while(dep[top[b]]>dep[a]+1){
        b=fa[top[b]];
    }
    int x=dep[b]-dep[a]-1;
    if(x<0)return 0;
    return id[b]>x?cid[id[b]-x]:0;
}
void init(){
    tot=0,Stop=0,Bcnt=0,icnt=0,cnt=0;
    for(int i=1;i<=n*2;i++){
        dfn[i]=0,low[i]=0,cut[i]=0,siz[i]=0,son[i]=0,dep[i]=0,fa[i]=0,top[i]=0,id[i]=0,cid[i]=0,head[i]=-1;
        vv[i].clear();
    }
}
int main()
{
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=1; i<=m; i++){
            int tu,tv;
            scanf("%d%d", &tu, &tv);
            add(tu,tv);
            add(tv,tu);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) Tarjan(i,0,i);
        }
        dfs(1,0);
        dfs2(1,1);
        scanf("%d",&q);
        int x,y;
        while(q--)
        {
            scanf("%d%d",&x,&y);
            int ans=n;
            if(dep[x]>dep[y])swap(x,y);
            int l=lca(x,y);
            //printf(" %d ",l);
            if(fa[l]==x){
                if(cut[x]){
                    ans-=n-siz[l]-1;
                }
                if(cut[y]){
                    ans-=siz[y]-1;
                }
            }else{
                if(cut[x]){
                    ans-=siz[x]-1;
                }
                if(cut[y]){
                    ans-=siz[y]-1;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}
/*
2
7 7
1 2
1 3
2 4
2 7
4 7
2 5
3 6
5
2 5
4 7
2 3
6 5
3 7
5 5
1 2
1 3
2 4
4 5
2 5
5
1 2
1 4
2 3
2 5
3 5
*/