B

Knights in the Zombie Land Input: Standard Input Output: Standard Output

In a far far away country named Zombie Land, there lived four knights Agrum, Bagrum, Chagrum and Dagrum. They were given order from their king Tagrum that if they see any zombie they should kill them immediately. One day while hunting for zombies they saw a beautiful girl zombie named Nagrum and all of them fell in love at the first sight. They went to Nagrum, expressed their love and asked her to choose one of them. As the knights always killed zombies, Nagrum wanted to take revenge. She told them she will marry one who will win the duel (though actually she will kill the winner because it is easier to kill one than four). Nagrum described the rule of the duel: The duel will be played in a large field divided into 1*1 squares. The field is R*C in size (R rows, C columns). A square may be denoted by its row and column number, (r, c) means the square at r-th row and c-th column where 1 ≤ r ≤ R and 1 ≤ c ≤ C.

Every Knight will stand on a square. A knight can attack another knight if they are not in the same row or column and has Manhattan distance 3 between their square. (Manhattan distance between two cells (r₁, c₁) and (r₂, c₂) is abs(r₁-r₂) + abs(c₁-c₂) where abs means absolute value) For example, if two knights are standing on the squares (3, 4) and (5, 5) then they may attack each other but if they are on (1,1) and (2,2) they cannot. Even if they are standing on (1, 3) and (4, 3) they cannot. There are some stony squares and knights won't stand on such square. You are given the positions of the stony squares, you are to output number of configurations for Agrum, Bagrum, Chagrum and Dagrum so that, Agrum may attack Bagrum, Bagrum may attack Chagrum, Chagrum may attack Dagrum and finally Dagrum may attack Agrum. To make the problem more interesting, let's add two more conditions, Agrum cannot attack Chagrum and Bagrum cannot attack Dagrum. Note that, X may attack Y means Y also may attack X which should be clear from the rule of attacking above. Two configurations will be considered different if any of the knights are positioned at different square.

Input

First line contains an integer, T (≤ 30) denoting number of test cases. Then there follows T test cases.

First line of each test case contains three integers, number of rows R (5 ≤ R ≤ 10⁵), number of columns C (5 ≤ C ≤ 10⁵) and number of stony squares (0 ≤ n ≤ 10⁵). Then there follows n lines containing row and column number of the stony squares. Given stony squares will always be inside the field. (Input file is huge, better to use faster I/O methods.)

Output

For each test case output the case number and the number of valid configurations. For clarity please see the sample input output.

Sample Input Output for Sample Input

2 10000 10000 1 1 1 5 5 6 2 2 2 4 4 2 4 4 3 3 3 1

Case 1: 4797120408 Case 2: 8

---