题目描述

JOHNKRAM 收到了一个字符串 $ S $，但他不喜欢这个串，他决定把它变成 $ T $。

JOHNKRAM 最近学习了一些后缀数据结构，他相信通过替换后缀可以实现一切操作。他有 $ m $ 种替换方式，每种替换方式包含两个等长的字符串 $ u $ 和 $ v $，如果当前 $ u $ 是 $ S $ 的后缀，则可以将 $ S $ 的后缀 $ u $ 替换成 $ v $。

现在 JOHNKRAM 希望你能帮他计算出，最少需要替换多少次才能将 $ S $ 变成 $ T $。

输入格式

一个测试点包含多组数据。
每组数据第一行包含两个字符串 $ S $ 和 $ T $ 以及一个整数 $ n $，意思如题所示。
接下来 $ n $ 行每行两个字符串 $ u $ 和 $ v $，表示一种替换方式。
输入文件以一个 . 结束。

输出格式

对于每一组数据，输出该组数据编号以及最小步数，如果无解输出 No Solution。格式参见样例。

样例

input

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

output

Case 1: 2
Case 2: No solution

数据范围与提示

对于 $ 30\% $ 的数据，字符串长度 $ \leq 1 $；
对于 $ 45\% $ 的数据，字符串长度 $ \leq 5 $；
对于 $ 100\% $ 的数据，字符串长度 $ \leq 20, 1 \leq n \leq 100 $，字符集为大小写字母。