The Happy Worm

Time Limit: 2 Seconds
Memory Limit: 65536 KB

The Happy Worm lives in an *m*n* rectangular field. There are *k* stones placed in certain locations of the field. (Each square of the field is either empty, or contains a stone.) Whenever the worm sleeps, it lies either horizontally or vertically, and stretches so that its length increases as much as possible. The worm will not go in a square with a stone or out of the field. The happy worm can not be shorter than 2 squares.

The question you are to answer is how many different positions this worm could be in while sleeping.

**Input Specification**

The first line of the input file contains a single integer *t* (1 <= *t* <= 11), the number of test cases, followed by the input data for each test case. The first line of each test case contains three integers m, n, and k (0 <= *m*,*n*,*k* <= 200000). The input for this test case will be followed by k lines. Each line contains two integers which specify the row and column of a stone. No stone will be given twice.

**Output Specification**

There should be one line per test case containing the number of positions the happy worm can be in.

**Sample Input**

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

**Sample Output**

9

Source:

**Asia 2004, Tehran (Iran), Sharif Preliminary**
Submit
Status