#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 int n, m;

 bool vis[][ << ];

 bool mark[ << ];

 int dp[ << ];

 vector<int > g[];

 void dfs(int u, int state)

 {

     vis[u][state] = true;

     mark[state] = true;

     for (int i = ; i < (int)g[u].size(); i++) {

         int v = g[u][i];

         if (!vis[v][state | ( << v)]) {

             dfs(v, state | ( << v));

         }

     }

 }

 int Solve(int state)

 {

     if (state == ) return ;

     if (dp[state] != -) return dp[state];

     int res = ;

     for (int i = state; i > ; i = (i - ) & state) {

         if (mark[i]) {

             res = min(res,  + Solve(state ^ i));

         }

     }

     return dp[state] = res;

 }

 int main()

 {

     int _case, t = ;

     scanf("%d", &_case);

     while (_case--) {

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

         for (int i = ; i < n; i++) g[i].clear();

         while (m--) {

             int u, v;

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

             u--, v--;

             g[u].push_back(v);

         }

         memset(vis, false, sizeof(vis));

         memset(mark, false, sizeof(mark));

         for (int i = ; i < n; i++) dfs(i,  << i);

         memset(dp, -, sizeof(dp));

         printf("Case %d: %d\n", t++, Solve(( << n) -));

     }

     return ;

 }