#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 150const int INF = 0x3f3f3f3f ;int dp[MAXN][MAXN];bool vis[MAXN][MAXN];int N,M,ans;void init(){    scanf("%d%d",&N,&M);    memset(dp,0x3f,sizeof(dp));    while (M--)    {        int u,v;        scanf("%d%d",&u,&v);        dp[u][v] = dp[v][u] = 1;    }    for (int k = 0; k < N; k++)        for (int i = 0; i < N; i++)          for (int j = 0; j < N; j++)           dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);    for (int i = 0; i < N; i++) dp[i][i] = 0;}int calcu(int s, int t){    int res[MAXN],cas = 0,cnt = 0;    for (int k = 0; k < N; k++)        if (dp[s][k] + dp[k][t] == dp[s][t]) res[cas++] = k;    for (int i = 0; i < cas; i++)        for (int j = i + 1; j < cas; j++)    {        int a = res[i] , b = res[j];        if(dp[a][b] == 1 && dp[s][a] != dp[s][b])            cnt++;    }    return cnt;}void slove(){    for (int i = 0; i < N; i++)        for (int j = i + 1; j < N; j++)    {        if (dp[i][j] != INF)            ans = max(ans,calcu(i,j));    }}int main(){    //freopen("sample.txt","r",stdin);    int T,kase = 1;    scanf("%d",&T);    while (T--)    {        init();        ans = 0;        slove();        printf("Case #%d: %d\n",kase++,ans);    }    return 0;}