#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll t;
    cin>>t;
    
    while (t--)
    {
        ll n,m;
        cin>>n>>m;
        ll k;
        cin>>k;
        vector <string> v(k+2);
        for (ll i=1;i<=k;i++)
        {
            cin>>v[i];
        }
        vector <vector <pair<ll,ll>>> g(2*n*m+1);
        for (char ch='a';ch<=('a'+(m-1));ch++)
        {
            for (ll num=1;num<=n;num++)
            {
                ll nd_num=(ch-'a')*(2*n);
                nd_num+=((num-1)*2);
                nd_num++;
                ll num1=num;
                char ch1=ch;
                    num1++;
                    ch1--;
                    while (num1<=n && ch1>='a')
                    {
                        ll nd_num1=(ch1-'a')*(2*n);
                        nd_num1+=(num1-1)*2;
                        nd_num1++;
                        g[nd_num].push_back({nd_num1,0});
                        num1++;
                        ch1--;
                    }
                    num1=num;
                    ch1=ch;
                    num1--;
                    ch1++;
                    while (num1>=1 && ch1<=('a'+(m-1)))
                    {
                        ll nd_num1=(ch1-'a')*(2*n);
                        nd_num1+=(num1-1)*2;
                        nd_num1++;
                        g[nd_num].push_back({nd_num1,0});
                        num1--;
                        ch1++;
                    }
                nd_num++;
                num1=num;
                ch1=ch;
                    num1++;
                    ch1++;
                    while (num1<=n && ch1<=('a'+(m-1)))
                    {
                        ll nd_num1=(ch1-'a')*(2*n);
                        nd_num1+=(num1)*2;
                        g[nd_num].push_back({nd_num1,0});
                        num1++;
                        ch1++;
                    }
                    num1=num;
                    ch1=ch;
                    num1--;
                    ch1--;
                    while (num1>=1 && ch1>='a')
                    {
                        ll nd_num1=(ch1-'a')*(2*n);
                        nd_num1+=(num1)*2;
                        g[nd_num].push_back({nd_num1,0});
                        num1--;
                        ch1--;
                    }
                nd_num--;
                g[nd_num].push_back({nd_num+1,1});
                g[nd_num+1].push_back({nd_num,1});
            }
        }
        map <ll,vector <ll>> dist_vectors;
        for (ll i=1;i<=k;i++)
        {
            char ch=v[i][0];
            string str=v[i].substr(1);
            ll r_num=stoll(str);
            ll nd_num=(ch-'a')*(2*n);
            nd_num+=(r_num-1)*2;
            nd_num++;
            dist_vectors[nd_num].resize(2*n*m+1,LLONG_MAX);
            dist_vectors[nd_num+1].resize(2*n*m+1,LLONG_MAX);
        }
        dist_vectors[2].resize(2*n*m+1,LLONG_MAX);
        set <pair<ll,ll>> s;
        vector <bool> visited(2*n*m+1,false);
        s.insert({0,2});
        dist_vectors[2][2]=0;
        while (!s.empty())
        {
            auto elem=s.begin();
            ll nd=(*elem).second;
            if (visited[nd])
            {
                s.erase(elem);
                continue;
            }
            ll w=(*elem).first;
            visited[nd]=true;
            s.erase(elem);
            for (auto child:g[nd])
            {
                if (!visited[child.first] && dist_vectors[2][child.first]>(child.second+w))
                {
                    dist_vectors[2][child.first]=(child.second+w);
                    s.insert({dist_vectors[2][child.first],child.first});
                }
            }
        }
        for (ll i=1;i<=k;i++)
        {
            char ch=v[i][0];
            string str=v[i].substr(1);
            ll r_num=stoll(str);
            ll nd_num=(ch-'a')*(2*n);
            nd_num+=(r_num-1)*2;
            nd_num++;
            vector <bool> vis(2*n*m+1,false);
            s.insert({0,nd_num});
            dist_vectors[nd_num][nd_num]=0;
            while (!s.empty())
            {
                auto elem=s.begin();
                ll nd=(*elem).second;
                if (vis[nd])
                {
                    s.erase(elem);
                    continue;
                }
                ll w=(*elem).first;
                vis[nd]=true;
                s.erase(elem);
                for (auto child:g[nd])
                {
                    if (!vis[child.first] && dist_vectors[nd_num][child.first]>(child.second+w))
                    {
                        dist_vectors[nd_num][child.first]=(child.second+w);
                        s.insert({dist_vectors[nd_num][child.first],child.first});
                    }
                }
            }
            nd_num++;
            vector <bool> vis1(2*n*m+1,false);
            s.insert({0,nd_num});
            dist_vectors[nd_num][nd_num]=0;
            while (!s.empty())
            {
                auto elem=s.begin();
                ll nd=(*elem).second;
                if (vis1[nd])
                {
                    s.erase(elem);
                    continue;
                }
                ll w=(*elem).first;
                vis1[nd]=true;
                s.erase(elem);
                for (auto child:g[nd])
                {
                    if (!vis1[child.first] && dist_vectors[nd_num][child.first]>(child.second+w))
                    {
                        dist_vectors[nd_num][child.first]=(child.second+w);
                        s.insert({dist_vectors[nd_num][child.first],child.first});
                    }
                }
            }
        }
        ll answer=LLONG_MAX;
        for (ll i=0;i<=(((1LL)<<k)-1);i++)
        {
            vector <ll> store;
            ll ind=1;
            for (ll j=1;j<=((1LL)<<(k-1));j*=2)
            {
                if ((i&j))
                {
                    char ch=v[ind][0];
                    string str=v[ind].substr(1);
                    ll r_num=stoll(str);
                    ll nd_num=(ch-'a')*(2*n);
                    nd_num+=(r_num-1)*2;
                    nd_num++;
                    store.push_back(nd_num);
                } else 
                {
                    char ch=v[ind][0];
                    string str=v[ind].substr(1);
                    ll r_num=stoll(str);
                    ll nd_num=(ch-'a')*(2*n);
                    nd_num+=(r_num)*2;
                    store.push_back(nd_num);
                }
                ind++;
            }
            sort(store.begin(),store.end());
            do 
            {
                ll temp=0;
                ll sz=k;
                temp+=(dist_vectors[2][store[0]]);
                for (ll j=1;j<sz;j++)
                {
                    temp+=(dist_vectors[store[j-1]][store[j]]);
                }
                answer=min(answer,temp);
            } while (next_permutation(store.begin(),store.end()));
        }
        cout<<answer<<"\n";
    }

    return 0;
}