Free Willy

Willy sits in a cage. The guard offers him his freedom if he solves a puzzle.

You are given two words of length $N$ and $P$ permutations that Willy may use. A permutation is written as a lowercase string that uses each of the first $N$ letters of the alphabet exactly once. Applying a permutation $q$ to a word $w$ produces a new word whose $i$-th letter is the $q_i$-th letter of $w$, where $q_i$ is the alphabet position of the $i$-th letter of $q$. Count a as 1 and b as 2.

Applying the permutation bcdefaghi to the word KULTURUKE gives ULTURKUKE. The first six letters rotate one place to the left and the rest stay where they are.

Willy may use only the given permutations, and he may use the same permutation more than once. The cage opens if he turns the first word into the second word with at most $L$ applications. Find the smallest number of applications.

The first line contains the number of test cases $T$. ($T \le 30$)

The first line of each test case contains $N$, $P$, and $L$, separated by spaces. ($1 \le N \le 26$, $1 \le P \le 10$, $1 \le L \le 10$)

The second line contains two words of length $N$, separated by a space. Both words consist of English letters only.

Each of the next $P$ lines contains one allowed permutation, a string that uses each of the first $N$ lowercase letters of the alphabet exactly once.

Print one line for each test case. Print the smallest number of applications needed to turn the first word into the second word, or whalemeat if it cannot be done with at most $L$ applications.