1 /*
2 * File: H.cpp
3 * Author: GongZhi
4 * Problem:
5 * Created on 2009年7月27日, 上午9:41
6 */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 #include <algorithm>
16 using namespace std;
17 const int MAX=1100;
18 struct node{
19 int x,y;
20 }data[MAX*MAX];
21 int n,m;
22 long long seg[MAX];
23 bool cmp(node a, node b)
24 {
25 return a.x<b.x||a.x==b.x&&a.y<b.y;
26 }
27 /*
28 *
29 */
30 int lowbit(int x)
31 {
32 return x^(x&(x-1));
33 }
34
35 int add(int x,int d)
36 {
37 while(x<=m)
38 {
39 seg[x]+=d;
40 x+=lowbit(x);
41 }
42 return 0;
43 }
44
45 long long sum(int x)
46 {
47 long long ans=0;
48 while(x>0)
49 {
50 ans+=seg[x];
51 x-=lowbit(x);
52 }
53 return ans;
54 }
55
56 int main() {
57 int kase;
58 int k,l;
59 scanf("%d",&kase);
60 for(k=1;k<=kase;k++){
61 scanf("%d%d%d",&n,&m,&l);
62 for(int i=0;i<l;++i)
63 scanf("%d%d",&data[i].x,&data[i].y);
64 sort(data,data+l,cmp);
65 memset(seg,0,sizeof(seg));
66 long long ans=0;
67 for(int i=0;i<l;++i)
68 {
69 add(data[i].y,1);
70 ans+=sum(m)-sum(data[i].y);
71 }
72 printf("Test case %d: %lld\n",k,ans);
73 }
74 return 0;
75 }
76