#include <bits/stdc++.h>
using namespace std;

void get_ac(){
        int E, W;
        cin>>E>>W;
        
        int x[E][W];
        for(int i = 0; i < E; i++){
                for(int j = 0; j < W; j++){
                        cin>>x[i][j];
                }
        }
        
        queue<pair<int,string>> q;
        q.push({0, ""});

        map<pair<int,string>, int> dep;
        dep[{0, ""}] = 0;
        
        int ans = INT_MAX;

        while(q.size()){
                auto cur = q.front(); q.pop();
                int ii = cur.first;
                string str = cur.second;
                
                
//                cout<<ii<<" "<<str<<" "<<dep[{ii, str}]<<"\n";
                if(ii == E){
                        ans= min(ans, int(dep[cur] + str.length()));
                        continue;
                }
                vector<int> cnt(W, 0);
                for(char c : str){
                        cnt[c - '0']++;
                }
                int next_bad = E;
                for(int j = ii; j < E; j++){
                        bool bad = 0;
                        for(int k = 0; k < W; k++){
                                if(cnt[k] != x[j][k]){
                                        bad = 1;
                                        break;
                                }
                        }
                        if(bad) {
                                next_bad= j;
                                break;
                        }
                }
                int current_depth= dep[cur];
                if(dep.find({next_bad, str}) == dep.end()){
                        q.push({next_bad, str}); dep[{next_bad, str}]= current_depth;
                }
                if(str.size() < 9){
                        for(int w= 0; w < W; w++){
                                str += (char)(w + '0');
                                if(dep.find({ii, str}) == dep.end()){
                                        q.push({ii, str});
                                        dep[{ii, str}]= current_depth + 1;
                                }
                                str.pop_back();
                        }
                }
                if(str.size()){
                        str.pop_back();
                        if(dep.find({ii, str}) == dep.end()){
                                q.push({ii, str});
                                dep[{ii, str}] = current_depth + 1;
                        }
                }
        }

        cout<<ans<<"\n";
}
int main() {
        cin.tie(0);
        cin.sync_with_stdio(0);
//
//
        int T = 1, tc = 1;
        cin>>T;
        while(T--){
                cout<<"Case #"<<tc++<<": ";
                get_ac();
        }
}