#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

#line 2 "graph/others/block-cut-tree.hpp"

#line 2 "graph/graph-template.hpp"

/**
 * @brief Graph Template(グラフテンプレート)
 */
template< typename T = int >
struct Edge {
    int from, to;
    T cost;
    int idx;

    Edge() = default;

    Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}

    operator int() const { return to; }
};

template< typename T = int >
struct Graph {
    vector< vector< Edge< T > > > g;
    int es;

    Graph() = default;

    explicit Graph(int n) : g(n), es(0) {}

    size_t size() const {
        return g.size();
    }

    void add_directed_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es++);
    }

    void add_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }

    void read(int M, int padding = -1, bool weighted = false, bool directed = false) {
        for(int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if(weighted) cin >> c;
            if(directed) add_directed_edge(a, b, c);
            else add_edge(a, b, c);
        }
    }

    inline vector< Edge< T > > &operator[](const int &k) {
        return g[k];
    }

    inline const vector< Edge< T > > &operator[](const int &k) const {
        return g[k];
    }
};

template< typename T = int >
using Edges = vector< Edge< T > >;
#line 2 "graph/others/low-link.hpp"

#line 4 "graph/others/low-link.hpp"

/**
 * @brief Low Link(橋/関節点)
 * @see http://kagamiz.hatenablog.com/entry/2013/10/05/005213
 * @docs docs/low-link.md
 */
template< typename T = int >
struct LowLink : Graph< T > {
public:
    using Graph< T >::Graph;
    vector< int > ord, low, articulation;
    vector< Edge< T > > bridge;
    using Graph< T >::g;

    virtual void build() {
        used.assign(g.size(), 0);
        ord.assign(g.size(), 0);
        low.assign(g.size(), 0);
        int k = 0;
        for(int i = 0; i < (int) g.size(); i++) {
            if(!used[i]) k = dfs(i, k, -1);
        }
    }

    explicit LowLink(const Graph< T > &g) : Graph< T >(g) {}

private:
    vector< int > used;

    int dfs(int idx, int k, int par) {
        used[idx] = true;
        ord[idx] = k++;
        low[idx] = ord[idx];
        bool is_articulation = false, beet = false;
        int cnt = 0;
        for(auto &to : g[idx]) {
            if(to == par && !exchange(beet, true)) {
                continue;
            }
            if(!used[to]) {
                ++cnt;
                k = dfs(to, k, idx);
                low[idx] = min(low[idx], low[to]);
                is_articulation |= par >= 0 && low[to] >= ord[idx];
                if(ord[idx] < low[to]) bridge.emplace_back(to);
            } else {
                low[idx] = min(low[idx], ord[to]);
            }
        }
        is_articulation |= par == -1 && cnt > 1;
        if(is_articulation) articulation.push_back(idx);
        return k;
    }
};
#line 3 "graph/connected-components/bi-connected-components.hpp"

template< typename T = int >
struct BiConnectedComponents : LowLink< T > {
public:
    using LowLink< T >::LowLink;
    using LowLink< T >::g;
    using LowLink< T >::ord;
    using LowLink< T >::low;

    vector< vector< Edge< T > > > bc;

    void build() override {
        LowLink< T >::build();
        used.assign(g.size(), 0);
        for(int i = 0; i < (int)used.size(); i++) {
            if(!used[i]) dfs(i, -1);
        }
    }

    explicit BiConnectedComponents(const Graph< T > &g) : Graph< T >(g) {}

private:
    vector< int > used;
    vector< Edge< T > > tmp;

    void dfs(int idx, int par) {
        used[idx] = true;
        bool beet = false;
        for(auto &to : g[idx]) {
            if(to == par && !exchange(beet, true)) continue;
            if(!used[to] || ord[to] < ord[idx]) {
                tmp.emplace_back(to);
            }
            if(!used[to]) {
                dfs(to, idx);
                if(low[to] >= ord[idx]) {
                    bc.emplace_back();
                    for(;;) {
                        auto e = tmp.back();
                        bc.back().emplace_back(e);
                        tmp.pop_back();
                        if(e.idx == to.idx) break;
                    }
                }
            }
        }
    }
};
#line 5 "graph/others/block-cut-tree.hpp"

/**
 * @brief Block Cut Tree
 * @see https://ei1333.hateblo.jp/entry/2020/03/25/010057
 */
template< typename T = int >
struct BlockCutTree : BiConnectedComponents< T > {
public:
    using BiConnectedComponents< T >::BiConnectedComponents;
    using BiConnectedComponents< T >::g;
    using BiConnectedComponents< T >::articulation;
    using BiConnectedComponents< T >::bc;

    vector< int > rev;
    vector< vector< int > > group;
    Graph< T > tree;

    explicit BlockCutTree(const Graph< T > &g) : Graph< T >(g) {}

    int operator[](const int &k) const {
        return rev[k];
    }

    void build() override {
        BiConnectedComponents< T >::build();
        rev.assign(g.size(), -1);
        int ptr = (int) bc.size();
        for(auto &idx : articulation) {
            rev[idx] = ptr++;
        }
        vector< int > last(ptr, -1);
        tree = Graph< T >(ptr);
        for(int i = 0; i < (int) bc.size(); i++) {
            for(auto &e : bc[i]) {
                for(auto &ver : {e.from, e.to}) {
                    if(rev[ver] >= (int) bc.size()) {
                        if(exchange(last[rev[ver]], i) != i) {
                            tree.add_edge(rev[ver], i, e.cost);
                        }
                    } else {
                        rev[ver] = i;
                    }
                }
            }
        }
        group.resize(ptr);
        for(int i = 0; i < (int) g.size(); i++) {
            group[rev[i]].emplace_back(i);
        }
    }
};

struct LowestCommonAncestor{
    int n,h;
    vector<vector<int>> g,par;
    vector<int> dep;
    LowestCommonAncestor(int n):n(n),g(n),dep(n){
        h=1;
        while((1<<h)<=n)h++;
        par.assign(h,vector<int> (n,-1));
    }
    void add_edge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void dfs(int v,int p,int d){
        par[0][v]=p;
        dep[v]=d;
        for(auto u:g[v]){
            if(u!=p)dfs(u,v,d+1);
        }
    }
    void build(int r){
        dfs(r,-1,0);
        for(int i=0;i<h-1;i++){
            for(int j=0;j<n;j++){
                if(par[i][j]>=0)par[i+1][j]=par[i][par[i][j]];
            }
        }
    }
    int lca(int u,int v){
        if(dep[u]>dep[v])swap(u,v);
        for(int i=0;i<h;i++){
            if((dep[v]-dep[u])&1<<i)v=par[i][v];
        }
        if(u==v)return u;
        for(int i=h-1;i>=0;i--){
            if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
        }
        return par[0][u];
    }
    int distance(int u,int v){
        return dep[u]+dep[v]-dep[lca(u,v)]*2;
    }
    // u->v
    int kthanc(int u,int v){
        int k = dep[v]-dep[u]-1;
        for (int i = 0; i < h and k; ++i) {
            if((1<<i)&k) {
                k -= (1<<i);
                v = par[i][v];
            }
        }
        return v;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    while (q--) {
        int n,m; cin >> n >> m;
        BlockCutTree<> bct(n);
        bct.read(m);
        bct.build();
        auto rev = bct.rev;
        auto vs = bct.group;
        auto g = bct.tree.g;
        int ptr = bct.bc.size();

        vector<int> cnt(g.size());
        for (int i = 0; i < n; ++i) {
            cnt[rev[i]]++;
        }
        LowestCommonAncestor lca(g.size());
        for (int i = 0; i < g.size(); ++i) {
            for (auto e:g[i]) {
                lca.g[e.from].push_back(e.to);
//                lca.add_edge(e.from, e.to);
            }
        }
        int rt = 0;
        lca.build(rt);
        vector<int> sum(g.size());
        auto dfs = [&](auto dfs,int s,int p) -> void {
            sum[s] = cnt[s];
            for (int t:lca.g[s]) {
                if(t == p) continue;
                dfs(dfs,t,s);
                sum[s] += sum[t];
            }
        };
        dfs(dfs,rt,-1);

        int qq; cin >> qq;
        while (qq--) {
            int a,b; cin >> a >> b;
            a--; b--;
            int i = rev[a], j = rev[b];
            if (i < ptr and j < ptr) {
                cout << n << "\n";
            }
            else if(i < ptr or j < ptr) {
                if(i < ptr) swap(i, j);
                // iが関節点
                int lc = lca.lca(i, j);
                if (lc == i) {
                    int res = sum[lca.kthanc(i,j)]+1;
                    cout << res << "\n";
                }
                else {
                    int res = n-sum[i]+1;
                    cout << res << "\n";
                }
            }
            else{
                int lc = lca.lca(i,j);
                if (lc != i and lc != j) {
                    int res = n-sum[i]-sum[j]+2;
                    cout << res << "\n";
                }
                else {
                    if(lca.dep[i] > lca.dep[j]) swap(i,j);
                    // i->j
                    int res = sum[lca.kthanc(i,j)]+1-sum[j]+1;
                    cout << res << "\n";
                }
            }
        }
    }
}