#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <map>
#include <list>
#include<iterator>
#include<set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for (int i=(a);i<(b);i++)
#define RFOR(i, b, a) for (int i=(b)-1;i>=(a);--i)
#define REP(i,N) FOR (i, 0, N)
#define RREP (i,N) RFOR (i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(),V.end()

#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979

typedef long long Int;
typedef unsigned long long UINT;
typedef vector<int> VI;
typedef pair <int, int> PII;

const int INF = 1000000000;
const int MAX = 207;
const int MAX2 = 2000;
const int BASE = 1000000000;

int m, n;
string A[MAX];
Int D[21][MAX][MAX];
set< pair<string, string> > S;

int main()
{
	//freopen("in.txt","r",stdin);
	freopen("suffix.in", "r", stdin);

	int test = 0;
	while (1)
	{
		++ test;
		cin >> A[0];
		if (A[0] == ".")
			break;

		cin >> A[1] >> m;
		n = 2;
		S.clear();
		FOR (i,0,m)
		{
			string a, b;
			cin >> a >> b;
			A[n ++] = a;
			A[n ++] = b;
			S.insert(MP(a, b));
		}

		m += 2;

		for (int len = 1; len <= SZ(A[0]); ++len)
		{
			FOR (i,0,n)
				FOR (j,0,n)
					D[len][i][j] = Int(INF) * INF;
			FOR (i,0,n)
			{
				if (SZ(A[i]) < len)
					continue;
				FOR (j,0,n)
				{
					if (SZ(A[j]) < len)
						continue;
					string s1 = "";
					string s2 = "";
					FOR (k,0,len)
						s1 += A[i][SZ(A[i])-len+k];
					FOR (k,0,len)
						s2 += A[j][SZ(A[j])-len+k];
					if (s1 == s2)
						D[len][i][j] = 0;
					if (S.find(MP(s1, s2)) != S.end())
						D[len][i][j] = min(D[len][i][j], 1LL);
					if (len > 1 && s1[0] == s2[0])
					{
						D[len][i][j] = min(D[len][i][j], D[len-1][i][j]);
					}
				}
			}
			FOR (t,0,n)
				FOR (i,0,n)
					FOR (j,0,n)
						D[len][i][j] = min(D[len][i][j], D[len][i][t] + D[len][t][j]);
		}
		Int res =  D[SZ(A[0])][0][1];
		cout << "Case " << test << ": ";
		if (res >= Int(INF) * INF)
			cout << "No solution" << endl;
		else
		cout << res << endl;
	}

	return 0;
}