Harry Potter is going to face a tough task in the Triwizard tournament. He has to go through a magical chessboard on a knight. The knight move is similar to the chess played by muggles – from the current square, it can move to a square which is horizontally 2 squares away and vertically 1 square away, or vertically 2 squares away and horizontally 1 square away. Obviously, it cannot go out of the board. There are some dangerous squares where it cannot go. Moreover, Harry needs to collect some magical weapons to complete the task. The position of those weapons will be known. He has to use all of them when he will approach the next task, so he has to collect all of the weapons.
There are also some dragons flying over the board which will constantly try to follow Harry. After reading a lot about these dragons, Hermione discovers an interesting fact. If he does not change the direction in consecutive moves, then it will be too easy for those dragons to kill him. Here, direction means the signed change in vertical and horizontal axis. If both of the signed value changes in vertical and horizontal direction remain same (in consecutive moves), it will be the end of his journey. For example, if he is currently in (2, 3) and came here from (1, 1), then he cannot go to (3, 5). He may go to (4, 4), (0, 2), (3, 1), (4, 2), (0, 4), (1, 5) or even go back to (1, 1). The amount of time required to complete one move also depends on the direction of the move. If the sign of change in both directions remain same, it takes no time (i.e. 0 seconds) to complete the move, otherwise it takes 1 second. For example, from (4, 4), it would take 0 second to go to (6, 5), (5, 6), (2, 3) or (3, 2), but it would take 1 second to go to (3, 6), (6, 3), (2, 5) or (5, 2).
Harry needs to complete this task as soon as possible by collecting all the weapons. Hermione could easily write a program to calculate the minimum time, but she is very busy with her research to understand the proper usage of all these new weapons. So she wants your help.
The first line of input contains a single integer T (1 <= T <= 120), which denotes the number of test cases to follow. For each test case, the first line contains 3 integers: m (1 <= m <= 100), n (1 <= n <= 100) and d (0 <= d <= m * n). Here m denotes the number of rows of the board, n denotes the number of columns of the board and d denotes the number of dangerous squares. Then d lines follow, where each line contains two integers: r and c, meaning (r, c) is the position of a dangerous square. Then there will be one line containing one integer w (0 <= w <= 5), which denotes the number of weapons. Then w lines follow, where each line contains two integers: r and c, meaning (r, c) is the position of a weapon. All row and columns are 0-indexed. No square will contain multiple weapons.
For each case, in a separate line, print the case number and the minimum amount of time required to start the journey from (0, 0) and end at (m – 1, n – 1) after collecting all the weapons. If it is not possible to complete the task, print “Impossible” (without quotes). Follow Sample Input and Output for details.
3 3 0
3 3 1
3 3 1
|Case 1: 2
Case 2: 4
Case 3: Impossible