#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn =  + ;

int e[maxn][maxn];

const LL MOD = 1e9 + ;

void add(LL &x, LL y) {

    x = (x + MOD + y) % MOD;

}

bool ok(int i, int j, int k) {

    return ((e[i][j] && e[j][k] && e[k][i]) || (!e[i][j] && !e[j][k] && !e[k][i]));

}

LL po[maxn];

int f;

void work() {

    memset(e, false, sizeof e);

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        e[u][v] = e[v][u] = ;

    }

    LL ans = po[n];

    add(ans, -(n + ));

    add(ans, -(n * (n - ) / ));

    LL t = ;

    for (int i = ; i <= n; ++i) {

        for (int j = i + ; j <= n; ++j) {

            for (int k = j + ; k <= n; ++k) {

                if (!ok(i, j, k)) t++;

            }

        }

    }

    for (int i = ; i <= n; ++i) {

        for (int j = i + ; j <= n; ++j) {

            for (int k = j + ; k <= n; ++k) {

                for (int h = k + ; h <= n; ++h) {

                    if (!ok(i, j, k) && !ok(i, j, h) && !ok(i, k, h) && !ok(j, k, h)) t++;

                }

            }

        }

    }

    for (int i = ; i <= n; ++i) {

        for (int j = i + ; j <= n; ++j) {

            for (int k = j + ; k <= n; ++k) {

                for (int h = k + ; h <= n; ++h) {

                    for (int ha = h + ; ha <= n; ++ha) {

                        if (!ok(i, j, k) && !ok(i, j, h) && !ok(i, k, h) && !ok(j, k, h) && !ok(i, j, ha) &&

                          !ok(i, k, ha) && !ok(i, h, ha) && !ok(j, k, ha) && !ok(j, h, ha) &&

                          !ok(k, h, ha)) t++;

                    }

                }

            }

        }

    }

    t %= MOD;

    add(ans, -t);

    printf("Case #%d: %lld\n", ++f, ans);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    po[] = ;

    for (int i = ; i <= maxn - ; ++i) {

        po[i] =  * po[i - ] % MOD;

    }

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}