1
#include<cstdio>
2
#include<cstring>
3
#include<vector>
4
#include<algorithm>
5
#define
MAXN 160
6
#define
MAXM 20
7
#define
MAXL 280
8
using
namespace
std;
9
int
n,m;
10
bool
land[MAXN][MAXM];
11
int
put[MAXL][MAXM],cnt[MAXL],tmp[MAXM],size;
12
vector<
int
>
G[MAXL];
13
int
dp[
2
][MAXL][MAXL];
14
bool
OK()
15
{
16
int
i,j,k,res;
17
for
(i=res=
0
;i<m;i++
)
18
{
19
if
(tmp[i])
20
{
21
for
(j=i;j<m&&tmp[i]==tmp[j];j++
);
22
k=j-
i;
23
if
(tmp[i]==
1
)
24
{
25
if
(k%
3
)
26
return
false
;
27
res+=k/
3
;
28
}
29
else
30
{
31
if
(k&
1
)
32
return
false
;
33
res+=k>>
1
;
34
}
35
i=j-
1
;
36
}
37
}
38
cnt[size]=
res;
39
return
true
;
40
}
41
void
DFS(
int
now)
42
{
43
if
(now==
m)
44
{
45
if
(OK())
46
memcpy(put[size++],tmp,
sizeof
(tmp));
47
}
48
else
49
{
50
int
i;
51
for
(i=
0
;i<
3
;i++
)
52
{
53
tmp[now]=
i;
54
DFS(now+
1
);
55
}
56
}
57
}
58
bool
Upper(
int
x,
int
y)
59
{
60
int
i;
61
for
(i=
0
;i<m;i++
)
62
{
63
if
(put[x][i]&&
put[y][i])
64
return
false
;
65
}
66
return
true
;
67
}
68
void
Init()
69
{
70
int
i,j;
71
size=
0
;
72
memset(land,
false
,
sizeof
(land));
73
memset(dp,
0
,
sizeof
(dp));
74
DFS(
0
);
75
for
(i=
0
;i<size;i++
)
76
{
77
G[i].clear();
78
for
(j=
0
;j<size;j++
)
79
{
80
if
(Upper(i,j))
81
G[i].push_back(j);
82
}
83
}
84
}
85
bool
Unfit(
int
r,
int
x)
86
{
87
int
i;
88
for
(i=
0
;i<m;i++
)
89
{
90
if
(land[r][i]&&
put[x][i])
91
return
true
;
92
}
93
return
false
;
94
}
95
bool
First(
int
x)
96
{
97
int
i;
98
for
(i=
0
;i<m;i++
)
99
{
100
if
(put[x][i]==
2
||put[x][i]&&land[
1
][i])
101
return
true
;
102
}
103
return
false
;
104
}
105
bool
Three(
int
x,
int
y,
int
k)
106
{
107
int
i;
108
for
(i=
0
;i<m;i++
)
109
{
110
if
(put[x][i]==
2
)
111
{
112
if
(put[y][i]||
land[k][i])
113
return
true
;
114
}
115
}
116
return
false
;
117
}
118
void
DoIt()
119
{
120
int
i,j,k,t,x,y,ans;
121
for
(ans=i=
0
;i<size;i++
)
122
{
123
if
(Unfit(
2
,i)||
First(i))
124
continue
;
125
dp[
0
][i][
0
]=
cnt[i];
126
}
127
for
(i=
3
;i<=n;i++
)
128
{
129
for
(j=
0
;j<size;j++
)
130
{
131
if
(Unfit(i,j))
132
continue
;
133
for
(k=
0
;k<G[j].size();k++
)
134
{
135
x=
G[j][k];
136
if
(Unfit(i-
1
,x)||Unfit(i-
1
,j))
137
continue
;
138
for
(t=
0
;t<G[x].size();t++
)
139
{
140
y=
G[x][t];
141
if
(Unfit(i-
2
,y)||Unfit(i-
2
,x)||Three(j,y,i-
2
))
142
continue
;
143
dp[i&
1
][j][x]=max(dp[i&
1
][j][x],dp[(i-
1
)&
1
][x][y]+
cnt[j]);
144
}
145
ans=max(ans,dp[i&
1
][j][x]);
146
}
147
}
148
}
149
printf(
"
%d\n
"
,ans);
150
}
151
int
main()
152
{
153
int
c,q,x,y;
154
scanf(
"
%d
"
,&
c);
155
while
(c--
)
156
{
157
scanf(
"
%d%d%d
"
,&n,&m,&
q);
158
Init();
159
while
(q--
)
160
{
161
scanf(
"
%d%d
"
,&x,&
y);
162
land[x][y-
1
]=
true
;
163
}
164
DoIt();
165
}
166
return
0
;
167
}
