Willy 被关在 Alcatraz 的监狱里。Jan Erik Vold 正在看守他，并向他提出了一个挑战：

“我通过依次应用以下置换，成功地将 KULTURUKE 转换为了 UKTURKULE： bcdefaghi cabfdeghi bcadefghi adcefgbhi cgabdefhi cdaefhgbi

这给了我创作伟大诗歌的灵感：KULTURUKE ULTURKUKE TULKURUKE ULTKURUKE UKTURULKE TLUKURUKE UKTURKULE

现在，我希望你使用同一组可用的置换来完成这个转换。我进行了 6 次置换，但如果你能用比我更少的次数完成它，我就打开牢笼！”

“这很简单，我只需要 4 次置换！”Willy 说，“你先应用 bcadefghi 得到 ULKTURUKE。然后应用 cdaefhgbi 得到 KTUURKULE。接着再次应用 bcadefghi 得到 TUKURKULE。最后再应用一次 bcadefghi 得到 UKTURKULE。”

“噢，看来你并不是一条又大又笨的鱼，”Jan Erik 说着拿出了钥匙。Willy 跳进大海，从此过上了幸福的生活！

输入格式

输入的第一行包含测试用例的数量 $T \le 30$。每个测试用例的第一行包含 $1 \le N \le 26$，$1 \le P \le 10$ 和 $1 \le L \le 10$。第二行包含两个长度为 $N$ 的单词。接下来有 $P$ 行，每行包含一个前 $N$ 个字母（小写）的允许置换。

输出格式

对于每个测试用例，输出一行，表示将第一个单词的字母转换为第二个单词所需应用允许置换的最小次数。如果无法在最多 $L$ 步内完成，则输出 “whalemeat”。

样例

样例输入 1

3
9 6 5
KULTURUKE UKTURKULE
bcdefaghi
cabfdeghi
bcadefghi
adcefgbhi
cgabdefhi
cdaefhgbi
9 5 4
kulturuke tlukuruke
bcdefaghi
cabfdeghi
bcadefghi
adcefgbhi
cgabdefhi
9 3 4
WILLFREEY FREEWILLY
bacdefghi
abghefdic
fecdbaigh

样例输出 1

4
whalemeat
4