#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 1101010

int n,m;
vector<int>V[sz];

vector<int>V2[sz];

int dfn[sz],low[sz],cc,T;
stack<int>st;
void tarjan(int x,int fa) {
    dfn[x]=low[x]=++cc;
    st.push(x);
    for (auto v:V[x]) if (v!=fa) {
        if (!dfn[v]) tarjan(v,x),chkmin(low[x],low[v]);
        else chkmin(low[x],dfn[v]);
    }
    if (fa&&low[x]>=dfn[fa]) {
        int y; ++T;
        do {
            y=st.top(); st.pop();
            V2[T+n].push_back(y),V2[y].push_back(T+n);
        } while (y!=x);
        V2[T+n].push_back(fa),V2[fa].push_back(T+n);
    }
}

int siz[sz],son[sz],top[sz],fa[sz],pre[sz];
void dfs1(int x,int fa) {
    if (x<=n) siz[x]=1;
    ::fa[x]=fa;
    for (auto v:V2[x]) if (v!=fa) {
        dfs1(v,x),siz[x]+=siz[v];
        if (siz[v]>siz[son[x]]) son[x]=v;
    }
}
void dfs2(int x,int fa,int tp) {
    dfn[x]=++cc; pre[cc]=x;
    if (son[x]) dfs2(son[x],x,tp);
    for (auto v:V2[x]) if (v!=fa&&v!=son[x]) {
        dfs2(v,x,v);
    }
    low[x]=cc;
}

void work() {
    cin>>n>>m;
    int x,y;
    rep(i,1,m) cin>>x>>y,V[x].push_back(y),V[y].push_back(x);
    T=cc=0;
    tarjan(1,0);
    cc=0;
    dfs1(1,0),dfs2(1,0,1);
    int Q; cin>>Q;
    while (Q--) {
        cin>>x>>y;
        if (dfn[x]>dfn[y]) swap(x,y);
        if (low[x]>=low[y]) {
            int z=y,zz=-1;
            while (top[z]!=top[x]) zz=top[z],z=fa[top[z]];
            int ans;
            if (z!=x) zz=pre[dfn[x]+1];
            ans=siz[zz]-siz[y]+2;
            cout<<ans<<'\n';
        }
        else cout<<n-siz[x]-siz[y]+2<<'\n';
    }
    rep(i,1,n+T) V[i].clear(),V2[i].clear(),dfn[i]=low[i]=son[i]=siz[i]=top[i]=pre[i]=fa[i]=0;
    cc=T=0;
    while (st.size()) st.pop();
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    int T; cin>>T;
    while (T--) work();
    return 0;
}