#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int T, n, m, t, u, v, q;
int dfsn[NMAX], lv[NMAX], low[NMAX], sz[NMAX], cnt[NMAX], par[NMAX][18];
vector<int> adj[NMAX];

void dfs(int x, int p){
    dfsn[x] = low[x] = ++t;
    sz[x] = 1;
    for(int& nx : adj[x]){
        if(nx == p) continue;
        if(!dfsn[nx]){
            lv[nx] = lv[x] + 1;
            par[nx][0] = x;
            dfs(nx, x);
            sz[x] += sz[nx];
            low[x] = min(low[x], low[nx]);
            if(low[nx] >= dfsn[x]) cnt[x] += sz[nx];
        }
        else low[x] = min(low[x], dfsn[nx]);
    }
    return;
}

int main(void){ 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> T;
    while(T--){
        cin >> n >> m;
        while(m--){
            cin >> u >> v;
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }

        dfs(1, -1);
        for(int j = 1; j < 18; j++)
            for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];

        cin >> q;
        while(q--){
            cin >> u >> v;
            if(lv[u] > lv[v]) swap(u, v);
            int p = v;
            for(int j = 17; j >= 0; j--)
                if(lv[p] - lv[u] > (1<<j)) p = par[p][j];
            // cout << u << ' ' << v << ' ' << p << '\n';
            if(par[p][0] == u) {
                int ans = sz[p] + 1 - cnt[v];
                if(low[p] < dfsn[u]) ans += n - 1 - sz[p] - cnt[v];
                cout << ans << '\n';
            }
            else cout << n - cnt[u] - cnt[v] << '\n';
        }

        // init
        t = 0;
        for(int i = 0; i <= n; i++) {
            dfsn[i] = low[i] = sz[i] = cnt[i] = lv[i] = 0;
            adj[i].clear();
        }
    }
    return 0;
}