Benjamin Franklin Gates (Ben) is an American historian, cryptologist and the youngest descendent of long line of treasure hunters. This time Ben is on the way to find a secret treasure and he is driven by a written clue given by his grandfather “The secret lies with Charlotte”. According to family history, the clue could lead to the fabled “National Treasure” fought over since Ancient Egypt and hidden by the Founding Fathers and Freemasons during the American Revolutionary War.
At last Ben found the area where the treasure has been kept. The area is an axis parallel rectangular grid with east and west side closed and north and south side open. Some grid cells contain trees and only one grid cell have the treasure. Ben knows the position of the treasure in the grid but he can’t just walk into the grid and collect the treasure because surface of the grid is full of garbage and Ben can get hurt if he walks into the grid.
There is a good and a bad news for Ben at this moment. The good news is Ben has brought his skateboard and he is going to collect the treasure from the grid using his skateboard. The bad news is he forgot how to control the skateboard. He can only start skating from a position in the northern row of the grid and go in a straight line from north to south direction but cannot stop it. If there is a tree in the line of his skating he will hit the tree and stop in the cell containing the tree. Otherwise he will get out of the grid. Ben can never pass through a tree cell and from a tree cell he can’t start his skating again. Ben can jump from a cell (tree or non-tree) to its two neighbor cells (east cell and west cell). It does not matter if the cell he just jumped into contains a tree or not. By one or more jumps he should go to a non-tree cell (if there is any) start his skating again to the south. Please note he can’t jump while skating. Also he will not hit a tree when jumping to a tree cell. To capture the treasure Ben has to go through the treasure cell or its west neighbor cell or east neighbor cell. Note that, the treasure is so small that Ben will not hit the treasure and stop in the treasure cell when skating but he can collect it on the way.
Ben will start from a cell of the north row of the grid and collect the treasure and get out from the south side with minimum number of hit with trees. He can’t get out of the grid from west and east side of the grid.
Given the information of the grid, find the minimum number of hits Ben will get with tree to collect the treasure and get out of the grid.
First line contains an integer T (T <= 100), number of test case. First line of each test case contains three integers N, M and K (1 <= N, M <= 1,000,000,000 and 0 <= K <= 1,000), number of rows from north to south, number of columns from west to east and number of tree cell in the grid respectively. Next line will contain two integers Rx and Ry (1 <= Rx <= N and 1 <= Ry <= M) denoting the position of the treasure, where Rx is the row number and Ry is the column number of the treasure. Next K lines will contain two space separated integers Xi and Yi (1 <= Xi <= N and 1 <= Yi <= M), position of the i-th tree, where Xi is the row number and Yi is the column number. The north west corner of the grid is recognized as (1, 1) and south east corner as (N, M), that means grid rows goes from north to south and column goes from west to east.
The treasure cell will not contain a tree.
For each test case print the test case number and “Impossible” without quotes if it is not possible to collect the treasure and get out of the grid. Otherwise print the minimum number of hits Ben has to get with trees.
5 5 4
5 5 4
5 5 5
5 5 5
|Case 1: 1
Case 2: 0
Case 3: Impossible
Case 4: 0