#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

namespace VBCC {

Vec<2, int> adj, bcc; // 1-base
vector<int> low, dfn;
int Time;
vector<int> bcc_id;
int bcc_cnt; // 1-base
vector<int> is_cut; // whether is av
vector<int> is_cir;
vector<int> st;
int top;

int n, lgmx;
Vec<2, int> badj, banc;
vector<int> bdep, bsz;

void dfs(int u, int pa = -1) {
    int child = 0;
    low[u] = dfn[u] = ++Time;
    st[top++] = u;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            dfs(v, u), ++child;
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v]) {
                is_cut[u] = 1, ++bcc_cnt;
                int t;
                do {
                    bcc_id[t = st[--top]] = bcc_cnt;
                    bcc[bcc_cnt].eb(t);
                } while (t != v);
                bcc_id[u] = bcc_cnt;
                bcc[bcc_cnt].eb(u);
            }
        } else if (dfn[v] < dfn[u] && v != pa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (pa == -1 && child < 2) is_cut[u] = 0;
}

void add_edge(int u, int v) {
    adj[u].eb(v), adj[v].eb(u);
}

void init(int _n) {
    n = _n;
    lgmx = __lg(2*n) + 1;

    Time = bcc_cnt = top = 0;
    adj.assign(n+1, 0);
    bcc.assign(n+1, 0);
    low.assign(n+1, 0);
    dfn.assign(n+1, 0);
    bcc_id.assign(n+1, 0);
    is_cut.assign(n+1, 0);
    is_cir.assign(2*n+1, 0); 
    st.assign(n+1, 0);

    badj.assign(2*n+1, 0);
    banc = Vec<2, int>(2*n+1, lgmx, 0);
    bdep.assign(2*n+1, 0);
    bsz.assign(2*n+1, 0);
}

void solve() {
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) dfs(i);
    }
    /// block-cut tree
    for (int i = 1; i <= n; ++i) {
        if (is_cut[i]) bcc_id[i] = ++bcc_cnt, is_cir[bcc_cnt] = 1;
        ++bsz[bcc_id[i]];
    }
    for (int i = 1; i <= bcc_cnt && !is_cir[i]; ++i) {
        for (int j : bcc[i]) {
            if (is_cut[j]) badj[i].eb(bcc_id[j]), badj[bcc_id[j]].eb(i);
        }
    }
}

void dfs_init_bct(int now, int lst = 0) {
    bdep[now] = bdep[lst] + 1;
    banc[now][0] = lst;
    for (int x : badj[now]) {
        if (x == lst) continue;
        dfs_init_bct(x, now);
        bsz[now] += bsz[x];
    }
}

void build_lca_bct() {
    for (int lay = 1; lay < lgmx; ++lay) {
        for (int i = 1; i <= 2*n; ++i) {
            banc[i][lay] = banc[ banc[i][lay-1] ][lay-1];
        }
    }
}

pii lca_bct(int u, int v) {
    if (bdep[u] < bdep[v]) swap(u, v);
    for (int lay = lgmx-1; lay >= 0; --lay) {
        if ((bdep[u] - bdep[v] - 1) >> lay & 1) u = banc[u][lay];
    }
    if (banc[u][0] == v) return {v, u};
    u = banc[u][0];
    
    for (int lay = lgmx-1; lay >= 0; --lay) {
        if (banc[u][lay] != banc[v][lay]) u = banc[u][lay], v = banc[v][lay];
    }
    return {banc[u][0], -1};
}

int get_subsz_bct(int rt, int v) {
    rt = bcc_id[rt], v = bcc_id[v];
    auto [lca, son] = lca_bct(rt, v);
    if (lca != v) return bsz[v];
    else return n - bsz[son];
}

} /// end of namespace VBCC

void solve() {
    int N, M; cin >> N >> M;
    
    VBCC::init(N);
    for (int i = 0, u, v; i < M; ++i) cin >> u >> v, VBCC::add_edge(u, v);
    VBCC::solve();
    
    VBCC::dfs_init_bct(1);
    VBCC::build_lca_bct();
    
    // debug(VBCC::bcc_id);
    // debug(VBCC::badj);
    // debug(VBCC::bsz);
    // debug(VBCC::is_cut);
    
    int Q; cin >> Q;
    for (int q = 1; q <= Q; ++q) {
        int u, v; cin >> u >> v;
        int ans = N;
        if (VBCC::is_cut[u]) ans -= VBCC::get_subsz_bct(v, u) - 1;
        if (VBCC::is_cut[v]) ans -= VBCC::get_subsz_bct(u, v) - 1;
        cout << ans << "\n";
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif