Republic of Korea

The Republic of Korea lies on the Korean Peninsula in East Asia. It is bordered by sea on three sides: the West Sea to the west, the East Sea to the east, and the South Sea to the south.

There are $N$ cities on the east coast and $M$ cities on the west coast. ($N \le 1000$, $M \le 1000$) On each coast the cities are numbered from $1$, in order from north to south.

The newly inaugurated president wants to build $K$ highways connecting the east coast to the west coast. Each highway is a straight road that connects exactly one east-coast city to exactly one west-coast city. (In reality a perfectly straight road bores and tires drivers and can cause accidents, so roads are deliberately given slopes and curves to prevent this.)

A rest stop is built at every point where two highways cross. At most $2$ highways cross at any single point. Given the highways, write a program that counts the number of points at which highways cross.

The first line contains the number of test cases $T$.

For each test case, the first line contains three integers $N$, $M$, and $K$, where $K$ is the number of highways.

Each of the next $K$ lines describes one highway with two integers: the first is the number of the east-coast city it connects, and the second is the number of the west-coast city.

The number of highways is at most $400{,}000$, and only inputs whose answer is at most $2^{63}-1$ are given.

For each test case, print one line in the form Test case X: Y, where $X$ is the test case number (starting from $1$) and $Y$ is the number of points at which the highways cross.