作为计算机程序员，你可能听说过正则表达式和上下文无关文法。这些是在小字符集上生成字符串集合（即形式语言）的丰富方法。还有其他一些更深奥的语言生成方法，例如树邻接文法、上下文敏感文法和无限制文法。本题使用了一种新的语言生成方法：后缀替换文法（suffix-replacement grammar）。

一个后缀替换文法由一个起始字符串 $S$ 和一组后缀替换规则组成。每条规则的形式为 $X \to Y$，其中 $X$ 和 $Y$ 是长度相等的字母数字字符串。该规则意味着，如果当前字符串的后缀（即最右侧的字符）是 $X$，则可以将该后缀替换为 $Y$。这些规则可以应用任意多次。

例如，假设有 4 条规则 $A \to B$、$AB \to BA$、$AA \to CC$ 和 $CC \to BB$。你可以通过应用三次规则将字符串 $AA$ 转换为 $BB$：$AA \to AB$（使用 $A \to B$ 规则），然后 $AB \to BA$（使用 $AB \to BA$ 规则），最后 $BA \to BB$（再次使用 $A \to B$ 规则）。但你也可以通过仅应用 2 条规则更快速地完成转换：$AA \to CC$，然后 $CC \to BB$。

你必须编写一个程序，读入一个后缀替换文法和一个字符串 $T$，并确定该文法的起始字符串 $S$ 是否可以转换为字符串 $T$。如果可以，程序还必须求出完成该转换所需的最少规则应用次数。

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含两个长度相等的字母数字字符串 $S$ 和 $T$（每个长度在 1 到 20 之间，由空格分隔），以及一个整数 $NR$（$0 \le NR \le 100$），表示规则的数量。

接下来的 $NR$ 行中，每行包含两个长度相等的字母数字字符串 $X$ 和 $Y$（每个长度在 1 到 20 之间，由空格分隔），表示 $X \to Y$ 是该文法的一条规则。

所有字符串均区分大小写。

最后一个测试用例之后紧跟一行，仅包含一个句点（.）。

输出格式

对于每个测试用例，输出测试用例编号（从 1 开始），后跟将 $S$ 转换为 $T$ 所需的最少规则应用次数。

如果无法进行转换，则输出 No solution。

请遵循样例输出的格式。

样例

输入 1

AA BB 4 
A B 
AB BA 
AA CC 
CC BB 
A B 3 
A C 
B C 
c B 
.

输出 1

Case 1: 2 
Case 2: No solution