text: #include <bits/stdc++.h>
  // #include <atcoder/all>
  // using namespace atcoder;
  typedef long long ll;
  typedef long double ld;
  #define rep(i,n) for(ll i=0;i<(n);i++)
  #define repr(i,n) for(ll i=(n-1);i>=0;i--)
  #define all(x) x.begin(),x.end()
  #define br cout << "\n";
  using namespace std;
  const long long INF = 1e10;
  const long long MOD = 1e9+7;
  using Graph = vector<vector<ll>>;
  template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
  template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}
  ll ceilll(ll a, ll b) {return (a + b-1) / b;} // if(a%b != 0) (a/b) + 1
  ll get_digit(ll a) {ll digit = 0; while(a != 0){a /= 10; digit++;} return digit;} // a != 0
  template<typename T> void vecdbg(vector<T>& v){ rep(i, v.size()){cerr << v[i] << " ";} br;}
  template<typename T> void vecvecdbg(vector<vector<T>>& v){ rep(i, v.size()){rep(j, v[i].size()){cerr << v[i][j] << " ";} br;}}
  ll POW(ll a, ll n){ ll res = 1; while(n > 0){ if(n & 1){ res = res * a; } a *= a; n >>= 1; } return res; }
  using P = pair<ll, ll>;
  const double PI = acos(-1);
  
  // 0 false, 1 true 
  // string number to int : -48 or - '0'
  // a to A : -32
  // ceil(a)  1.2->2.0
  // c++17	g++ -std=c++17 a.cpp
  // global vector -> 0 initialization
  // DONT FORGET TO INTIALIZE
  // The type of GRID is CHAR. DONT USE STRING
  // If the result in local and judge is different, USE CODETEST!!
  // (a * b)over flow?   if(a > INF / b){ /* overflow */}
  
  int main() {
      std::cout << std::fixed << std::setprecision(15);
      ll t; cin >> t;
      rep(T, t){
          string s; cin >> s;
          ll K; cin >> K;
          vector<vector<ll>> d(26, vector<ll>(26, INF));
          rep(i, 26) d[i][i] = 0;
          rep(i, K){
              string t; cin >> t;
              ll l = t[0] - 'A', r = t[1] - 'A';
              d[l][r] = 1;
          }
  
          rep(k, 26){
              rep(i, 26){
                  rep(j, 26){
                      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                  }
              }
          }
  
          ll ans = INF;
          rep(i, 26){
              ll goal = i;
              ll tmp = 0;
              rep(j, s.size()){
                  ll now = s[j] - 'A';
                  tmp += d[now][goal];
              }
              ans = min(ans, tmp);
          }
  
          if(ans == INF) cout << "Case #" << T+1 << ": " << -1 << '\n';
          else cout << "Case #" << T+1 << ": " << ans << '\n';
  
  
      }
  
  }