Problem F
Looking for a New Place
Input: Standard Input

Output: Standard Output

 

It has been just over three months since SH and TR got married and they are already grossed out living at their current place. All the day-to-day hassles, crowds, nastiness and anxiety of living in the thick of things are now simply unendurable!  It’s high time that they looked for a new place in the suburban area where everything is quiet and peaceful. 

There was a recent ad in the newspaper by the ‘New-Couple Placement Company’ (NCPC) that is offering cheap plots just outside the city. TR, being the decision maker of the family, has contacted one of the brokers of NCPC and has shown interest to buy a new piece of land.  The broker has provided them with the details of available spaces from which they can choose their desired plot.

The area under the possession of NCPC can be modeled as a rectangular grid of size N x M. Each cell of the grid is either empty or blocked. Empty cells represent available spaces and the blocked ones are those that are already bought by some other party. SH and TR have got a budget that is big enough for buying K empty cells. K can have a maximum value of 6, thanks to straitened circumstances that SH and TR are presently in. All the K empty cells that will be bought by them have to be connected pair-wise. Two cells are connected if you can start from one and reach the other passing through only cells bought by you. You can move 4 ways – north, east, south and west.

How many ways can you select K cells that satisfies the above conditions?

Example:

.#.
...
##.
..#

Consider the grid above where the dimension is 4 x 3 and K = 3. Dots(.) represent empty cells and hashes(#) represent occupied cells.

B#.
BB.
##.
..#

 

.#.
BBB
##.
..#

 

.#B
.BB
##.
..#

 

.#.
.BB
##B
..#

 

.#B
..B
##B
..#

 

There are 5 ways to buy 3 cells, as shown above. B indicates the bought cells!

 

 
 
 

 

Input

The first line of input is an integer T(T<100) that gives you the number of test cases. Each case starts with a line containing 3 integers in the order N, M and K. 1 ≤ N, M ≤ 1000 and 1 ≤ K ≤ 6. The meanings of these variables are mentioned above. The next line contains an integer X(0≤X≤100) that indicates the number of cells that are blocked. The next line gives X pairs of integers in the order R1 C1 R2 C2 R3 C3 … RX CX. Each pair, Ri Ci, gives the coordinate of a cell that is blocked. All these pairs will have distinct coordinates and will be inside the grid.
Top-Left corner of the grid has a coordinate of (1, 1) and that of bottom right has a coordinate of (N, M).

 

Output

For each case, output the case number first followed by the required result.

 

Sample Input                             Output for Sample Input

3

4 3 3

4

1 2 3 1 3 2 4 3

2 2 4

0

 

10 10 1

1

3 4

Case 1: 5

Case 2: 1

Case 3: 99

Note:
The first case is delineated in the description above.