#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, m;
const int maxN = 52;
int id[maxN][maxN];
ll good = 0;
int Q[maxN];
int topQ = 0;
ll mask[2][maxN];
int INTER_EDGE = 0;
int edges[maxN * 2];
int A[maxN * maxN], B[maxN * maxN];
bool run_dfs(int tp) {
    topQ = 0;
    Q[topQ++] = 0;
    ll not_used = ((1LL << n) - 1) ^ 1;
    for (int i = 0; i < topQ; i++) {
        int x = Q[i];
        while ((not_used & mask[tp][x]) > 0) {
            int f = __builtin_ctzll(not_used & mask[tp][x]);
            assert(not_used & (1LL << f));
            if (tp == 0) {
                edges[INTER_EDGE++] = id[x][f];
            }
            else {
                edges[INTER_EDGE++] = id[f][x];
            }
            not_used ^= (1LL << f);
            Q[topQ++] = f;
        }
    }
    return not_used;
}
int ITER = 0;
int bad[maxN * maxN];
void rec(int cnt, vector<int>& cant_del) {
    INTER_EDGE = 0;
    ll p0 = run_dfs(0);
    ll p1 = run_dfs(1);
    if (p0 != 0 || p1 != 0) return;
    if (cnt == 3) {
        good++;
        return;
    }
    ITER++;
    for (int u : cant_del) {
        bad[u] = ITER;
    }
    vector<int> cnd;
    for (int i = 0; i < INTER_EDGE; i++) {
        cnd.emplace_back(edges[i]);
    }
    sort(cnd.begin(), cnd.end());
    cnd.erase(unique(cnd.begin(), cnd.end()), cnd.end());

    vector<int> add_info = cant_del;
    vector<int> to_del;
    for (int t : cnd) {
        if (bad[t] != ITER) {
            to_del.emplace_back(t);
            add_info.emplace_back(t);
        }
    }

    int lft = m - (int)add_info.size();
    assert(lft >= 0);
    if (cnt == 2) {
        good += lft;
    }
    else if (cnt == 1) {
        good += (lft * (lft - 1)) / 2;
    }
    else {
        good += (1LL * lft * (1LL * lft - 1) * (lft - 2)) / 6;
    }
    //delete one
    if (cnt + 1 <= 3) {
        for (int t : to_del) {
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
            rec(cnt + 1, add_info);
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
        }
    }
    if (cnt + 2 <= 3) {
        for (int t : to_del) {
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
            for (int f : to_del) {
                if (t < f) {
                    mask[0][A[f]] ^= (1LL << B[f]);
                    mask[1][B[f]] ^= (1LL << A[f]);
                    rec(cnt + 2, add_info);
                    mask[0][A[f]] ^= (1LL << B[f]);
                    mask[1][B[f]] ^= (1LL << A[f]);
                }
            }
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
        }
    }
    if (cnt + 3 <= 3) {
        for (int t : to_del) {
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
            for (int f : to_del) {
                if (t < f) {
                    mask[0][A[f]] ^= (1LL << B[f]);
                    mask[1][B[f]] ^= (1LL << A[f]);
                    for (int r : to_del) {
                        if (f < r) {
                            mask[0][A[r]] ^= (1LL << B[r]);
                            mask[1][B[r]] ^= (1LL << A[r]);
                            rec(cnt + 3, add_info);
                            mask[0][A[r]] ^= (1LL << B[r]);
                            mask[1][B[r]] ^= (1LL << A[r]);
                        }
                    }
                    mask[0][A[f]] ^= (1LL << B[f]);
                    mask[1][B[f]] ^= (1LL << A[f]);
                }
            }
            mask[0][A[t]] ^= (1LL << B[t]);
            mask[1][B[t]] ^= (1LL << A[t]);
        }
    }
}
void solve() {
    cin >> n >> m;
    ll ans = (1LL * m * (m - 1) * (m - 2)) / 6;
    memset(id, -1, sizeof id);
    memset(mask, 0, sizeof mask);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        A[i] = x, B[i] = y;
        id[x][y] = i;
        mask[0][x] |= (1LL << y);
        mask[1][y] |= (1LL << x);
    }
    good = 0;
    vector<int> P;
    rec(0, P);
    cout << ans - good << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}