Castle Walls

In medieval times, knights commanded large armies of peasants. To storm a castle, the peasants line up in front of the castle wall and throw their grappling hooks over it. If a hook is not thrown straight, two hooks may cross, which makes it impossible for those two peasants to climb the wall. Well-trained peasants therefore never let their hooks cross.

Because of the recent Arthur–Claire Marriage (ACM), two peasant armies must be merged. Sir Arthur's peasants wear blue and Madame Claire's peasants wear red. When they practice together, the two armies mix in front of a wall and, on command, everyone throws their hooks. Thanks to their training, two hooks of the same color never cross, but a blue hook may cross a red one.

To measure how well the armies have merged, count how many distinct blue–red pairs of peasants have crossing hooks.

There are $n$ blue and $m$ red peasants. The standing positions in the line are numbered $1$ to $n + m$, and the positions on the castle wall are numbered $1$ to $n + m$ as well; wall position $i$ is directly opposite line position $i$. A hook thrown from line position $i$ to wall position $j$ crosses a hook thrown from $k$ to $l$ if and only if

$(i < k \text{ and } j \ge l) \quad\text{or}\quad (i > k \text{ and } j \le l).$

No two peasants share a line position, and hooks of the same color never cross. Two hooks of different colors may be thrown to the same wall position, in which case they are also considered to cross.

The first line contains the number of scenarios.

Each scenario begins with a line containing two integers $n$ and $m$, the number of blue and red peasants ($1 \le n, m \le 30000$).

The next $n$ lines describe the blue peasants, followed by $m$ lines for the red peasants. Each of these lines contains two integers $i$ and $j$ ($1 \le i, j \le n + m$): the peasant stands at line position $i$ and threw a hook to wall position $j$.

For each scenario, print a line Scenario #i:, where i is the scenario number starting from $1$, followed by a line containing the number of distinct blue–red peasant pairs whose hooks cross. Print a blank line between consecutive scenarios.