Setting

Computer scientists are jolly good people that enjoy a bit of fun. The latest craze is a game that consists of four wheels, each labeled (clockwise) with all the digits from zero to nine. The topmost digits of the four wheels form an integer between 0 and 9999. Each wheel has two buttons, one each to rotate it one digit to the left or to the right. Starting with an initial configuration, the aim of the game is to get to a final configuration without passing through a number of forbidden configurations in the process.

More formally, we start with an initial configuration of the wheels, with the topmost digits forming the integer \(S_1S_2S_3S_4\). You will be given a set of \(n\) forbidden configurations \(F_{i_1}F_{i_2}F_{i_3}F_{i_4}\) (\(1 \leq i \leq n\)) and a target configuration \(T_1T_2T_3T_4\). Your job is to write a program to calculate the minimum number of button presses required to transform the initial configuration to the target configuration without passing through a forbidden one.

Input

The first line of the input contains an integer \(N\) giving the number of test cases. A blank line then follows.

The first line of each test case contains the initial configuration of the wheels, specified by four digits. Two consecutive digits are separated by a space. The next line contains the target configuration. The third line contains an integer \(n\) giving the number of forbidden configurations. Each of the following \(n\) lines contains a forbidden configuration. There is a blank line between two consecutive input sets.

Output

For each test case in the input print a line containing the minimum number of button presses required. If the target configuration is not reachable, print -1.

Sample Input

2

8 0 5 6
6 5 0 8
5
8 0 5 7
8 0 4 7
5 5 0 8
7 5 0 8
6 4 0 8

0 0 0 0
5 3 1 7
8
0 0 0 1
0 0 0 9
0 0 1 0
0 0 9 0
0 1 0 0
0 9 0 0
1 0 0 0
9 0 0 0

Sample Output

14
-1

This is challenge 10067 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 1.17
Points (changes over time) 10
Tried by 10 users
Solved by 8 users

Global ranking

# Name Runtime Points worth
1 Marvin 0.24 18
2 Bjoern 0.27 16
3 JB 0.30 15
4 贝尔恩德 0.38 11
5 ,s/java/NaN/gi 0.41 11
6 Dark 0.83 5
7 Mac 1.50 3
8 Skøgland 5.39 1