Server Time: Wed Sep 23, 2020 6:47 am
Welcome ( logout
H - A Toy Company
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

The toy company "Babies Toys" has hired you to help develop educational toys. The current project is a word toy that displays three letters at all times. Below each letter are two buttons that cause the letter above to change to the previous or next letter in alphabetical order. So, with one click of a button the letter 'c' can be changed to a 'b' or a 'd'. The alphabet is circular, so for example an 'a' can become a 'z' or a 'b' with one click.

In order to test the toy, you would like to know if a word can be reached from some starting word, given one or more constraints. A constraint defines a set of forbidden words that can never be displayed by the toy. Each constraint is formatted like "X X X", where each X is a string of lowercase letters. A word is defined by a constraint if the ith letter of the word is contained in the ith X of the constraint. For example, the constraint "lf a tc" defines the words "lat", "fat", "lac" and "fac".

You will be given a string start, a string finish, and some forbidden strings. Calculate and return the minimum number of button presses required for the toy to show the word finish if the toy was originally showing the word start. Remember, the toy must never show a forbidden word. If it is impossible for the toy to ever show the desired word, return -1.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case begins with a blank line and two strings in two lines, start and finish both having exactly three characters each. The next line contains an integer n (1 ≤ n ≤ 50) denoting the number of forbidden words. Each of the next n lines will contain three strings each, separated by a single space. Each string (all the three strings) in a line will contain only distinct letters. Remember that start or finish can be forbidden. You can assume that all the characters are lowercase.

Output

For each case of input you have to print the case number and desired result.

Sample Input

Output for Sample Input

3

 

aab

zna

8

a a a

a a z

a z a

z a a

a z z

z a z

z z a

z z z

 

aaa

aaa

0

 

aab

nnn

1

a a ab

Case 1: 15

Case 2: 0

Case 3: -1

 


Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan