//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define notall(x) x.begin()+1,x.end()
#define all(x) x.begin(),x.end()
#define mul_t int _t;cin>>_t;while(_t--)
const int int_inf = 1000000100;
const ll ll_inf = 1000000000000000100;
//writers
template<class T>
void writeln(const T &t) {
    cout << t << '\n';
}
template<class T, class...args>
void writeln(const T &t, const args &...rest) {
    cout << t << ' ';
    writeln(rest...);
}
template<class T1>
void writeln(const vector<T1> &v) {
    for (auto c : v)
        cout << c << ' ';
    cout << ' ' << '\n';
}
template<class T1, class T2>
void writeln(const vector<T1> &v, T2 n) {
    for (T2 i = 1; i <= n; i++)
        cout << v[i] << ' ';
    cout << ' ' << '\n';
}
template<class T1, class T2>
void writeln(const pair<T1, T2> p) {
    cout << p.first << ' ' << p.second << ' ' << '\n';
}

vector<array<int,2>>dis{{0,-1},{-1,0},{0,1},{1,0}};
int n,m,k,ans;
ll st;
bool check(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m;
}
int get(int x,int y,ll nowst)
{
    int z=x*m+y;
    return nowst>>z&1;
}
void dfs(ll st)
{
    ans=min(ans,__builtin_popcountll(st));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(get(i,j,st))
            {
                for(int k=0;k<4;k++)
                {
                    int x=i+dis[k][0],y=j+dis[k][1],xx=x+dis[k][0],yy=y+dis[k][1];
                    if(check(x,y)&&check(xx,yy)&&get(x,y,st)&&(!get(xx,yy,st)))
                    {
                        ll tmpst=st;
                        tmpst^=1ll<<(i*m+j);
                        tmpst^=1ll<<(x*m+y);
                        tmpst^=1ll<<(xx*m+yy);
                        dfs(tmpst);
                    }
                }
            }
        }
}
void solve(){
    cin>>n>>m>>k;
    st=0,ans=int_inf;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        --x,--y;
        int z=x*m+y;
        st|=1ll<<z;
    }
    dfs(st);
    writeln(ans);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);
    mul_t
    solve();
}
/*
1.深呼吸，不要紧张，慢慢读题，读明白题，题目往往比你想的简单。
2.暴力枚举:枚举什么，是否可以使用一些技巧加快枚举速度（预处理、前缀和、数据结构、数论分块）。
3.贪心:需要排序或使用数据结构（pq）吗，这么贪心一定最优吗。
4.二分：满足单调性吗，怎么二分，如何确定二分函数返回值是什么。
5.位运算：按位贪心，还是与位运算本身的性质有关。
6.数学题：和最大公因数、质因子、取模是否有关。
7.dp：怎么设计状态，状态转移方程是什么，初态是什么，使用循环还是记搜转移。
8.搜索：dfs 还是 bfs ，搜索的时候状态是什么，需要记忆化吗。
9.树上问题：是树形dp、树上贪心、或者是在树上搜索。
10.图论：依靠什么样的关系建图，是求环统计结果还是最短路。
11.组合数学：有几种值，每种值如何被组成，容斥关系是什么。
12.交互题：log(n)次如何二分，2*n 次如何通过 n 次求出一些值，再根据剩余次数求答案。
13.如果以上几种都不是，多半是有一个 point 你没有注意到，记住正难则反。
*/