In this problem we will be considering a game played with four wheels. Digits ranging from 0 to 9 are printed consecutively (clockwise) on the periphery of each wheel. The topmost digits of the wheels form a four-digit integer. For example, in the following figure the wheels form the integer 8056. Each wheel has two buttons associated with it. Pressing the button marked with a left arrow rotates the wheel one digit in the clockwise direction and pressing the one marked with the right arrow rotates it by one digit in the opposite direction. The game starts with an initial configuration of the wheels. Say, in the initial configuration the topmost digits form the integer S1S2S3S4. You will be given some (say, n) forbidden configurations Fi1 Fi2 Fi3 Fi4 (1 ≤ i ≤ n) and a target configuration T1T2T3T4. Your job will be to write a program that can calculate the minimum number of button presses required to transform the initial configuration to the target configuration by never passing through a forbidden one. Input The first line of the input contains an integer N giving the number of test cases to follow. The first line of each test case contains the initial configuration of the wheels specified by 4 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 then print ‘-1’. Sample Input 2 8056 6508 5
2/2 8057 8047 5508 7508 6408 0000 5317 8 0001 0009 0010 0090 0100 0900 1000 9000 Sample Output 14 -1