프리 윌리

윌리는 우리에 갇혀 있다. 감시원이 자유를 걸고 문제를 낸다.

길이가 $N$인 단어 두 개와 쓸 수 있는 순열 $P$개가 주어진다. 순열은 알파벳 앞쪽 $N$글자를 한 번씩 사용한 소문자 문자열로 적는다. 단어 $w$에 순열 $q$를 적용하면 새 단어가 나오고, 새 단어의 $i$번째 글자는 $w$의 $q_i$번째 글자다. 여기서 $q_i$는 $q$의 $i$번째 글자가 알파벳에서 몇 번째인지를 뜻한다. a는 1, b는 2로 센다.

순열 bcdefaghi를 단어 KULTURUKE에 적용하면 ULTURKUKE가 된다. 앞의 여섯 글자가 왼쪽으로 한 칸씩 돌고 나머지는 제자리에 남는다.

윌리는 주어진 순열만 쓸 수 있고, 같은 순열을 여러 번 써도 된다. 순열 적용을 $L$번 이내로 반복해서 첫 번째 단어를 두 번째 단어로 바꾸면 우리가 열린다. 최소 몇 번 적용하면 되는지 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 30$)

각 테스트 케이스의 첫 줄에는 $N$, $P$, $L$이 공백으로 구분되어 주어진다. ($1 \le N \le 26$, $1 \le P \le 10$, $1 \le L \le 10$)

둘째 줄에는 길이가 $N$인 단어 두 개가 공백으로 구분되어 주어진다. 두 단어는 영문자로만 이루어진다.

이어지는 $P$개의 줄에는 쓸 수 있는 순열이 한 줄에 하나씩 주어진다. 각 순열은 알파벳 앞쪽 $N$글자를 소문자로 한 번씩 사용한 문자열이다.

각 테스트 케이스마다 한 줄씩 출력한다. 첫 번째 단어를 두 번째 단어로 바꾸는 데 필요한 최소 적용 횟수를 출력하고, $L$번 이내로 바꿀 수 없으면 whalemeat을 출력한다.