#include <bits/stdc++.h>
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 ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<LL, LL> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 110;

pair<string, string> A[MAX];
int n;

map<pair<int, pair<string, string> >, LL > M;

string suf(int len, string& s)
{
    string res;
    FOR (i, 0, len)
    {
        res += s[i + SZ(s) - len];
    }

    return res;
}

string pref(int len, string& s)
{
    string res;
    FOR (i, 0, len)
    {
        res += s[i];
    }

    return res;
}

LL go(string a, string b, int st)
{
    if (a == b) return 0;
    if (M.count(MP(st, MP(a, b)))) return M[MP(st, MP(a, b))];

    M[MP(st, MP(a, b))] = LINF;

    LL res = LINF;

    FOR (i, st, n)
    {
        int c = SZ(A[i].first);

        if (pref(SZ(a) - c, a) != pref(SZ(a) - c, b)) continue;

        LL left = go(suf(c, a), A[i].first, i+1);
        if (left == LINF) continue;

        LL right = go(A[i].second, suf(c, b), i+1);

        if (right == LINF) continue;

        res = min(res, left + right + 1);
    }

    M[MP(st, MP(a, b))] = res;

    return res;
}

bool cmp(const pair<string, string>& a, const pair<string, string>& b)
{
    return SZ(a.first) > SZ(b.first);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //ios::sync_with_stdio(false); cin.tie(0);

    int test = 0;
    while(true)
    {
        test++;
        string a;
        cin>>a;
        if (a == ".") break;
        string b;
        cin>>b>>n;
        FOR (i, 0, n)
        {
            cin>>A[i].first>>A[i].second;
        }

        sort(A, A+n, cmp);

        M.clear();

        LL res = go(a, b, 0);

        cout<<"Case "<<test<<": ";
        if (res == LINF) cout<<"No solution\n";
        else cout<<res<<"\n";
    }
}