提示: 欢迎访问OurACM平台。
Problem 1176 The Happy Worm

Accept: 59    Submit: 208
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

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

The first line of the input 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 (1 <= m,n <= 100000 , 0<= k <= 140000). 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

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

Iran 2004

Submit  Back  Status  Discuss