#include <stdio.h>

 #include <iostream>

 #include <string.h>

 #include <queue>

 #include <stack>

 using namespace std;

 const int N=;

 const int INF=-<<;

 struct node

 {

     int u,v,w;

     int next;

 } edge1[N*],edge2[N*];//edge1[]存的是原始图的边，edge2[]存的是缩点后的边

 int low[N],dfn[N],sccno[N];//sccno[i]表示点i所属于的连通分量的编号

 int dis[N],head1[N],head2[N],val[N];//val[]存储每个连通分量的价值

 int n,m,scc_cnt,cnt,dfs_clock;

 bool vis[N];

 stack<int>S;

 void init()

 {

     cnt = ;

     scc_cnt = ;

     dfs_clock = ;

     memset(val,,sizeof(val));

     memset(low,,sizeof(low));

     memset(dfn,,sizeof(dfn));

     memset(sccno,,sizeof(sccno));

     memset(head1,-,sizeof(head1));

     memset(head2,-,sizeof(head2));

 }

 void add(int u,int v,int w,node *edge,int *head)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = head[u];

     head[u] = cnt++;

 }

 void Tarjan(int u)//求强连通分量

 {

     low[u]=dfn[u]=++dfs_clock;

     S.push(u);

     for (int i = head1[u]; i!=-; i=edge1[i].next)

     {

         int v = edge1[i].v;

         if (!dfn[v])

         {

             Tarjan(v);

             low[u]=min(low[u],low[v]);

         }

         else if (!sccno[v])

         {

             low[u]=min(low[u],dfn[v]);

         }

     }

     if (low[u]==dfn[u])

     {

         ++scc_cnt;

         while()

         {

             int v = S.top();

             S.pop();

             sccno[v] = scc_cnt;

             if (v==u)

                 break;

         }

     }

 }

 void spfa(int s)//求缩点后的最长路

 {

     for (int i = ; i <= n*m; i++)

     {

         dis[i]=INF;

         vis[i]=false;

     }

     dis[s] = ;

     queue<int>q;

     q.push(s);

     vis[s] = true;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         vis[u]=false;

         for (int i = head2[u]; i!=-; i=edge2[i].next)

         {

             int v = edge2[i].v;

             int w = edge2[i].w;

             if (dis[v] < dis[u]+w)

             {

                 dis[v] = dis[u]+w;

                 if (!vis[v])

                 {

                     q.push(v);

                     vis[v]=true;

                 }

             }

         }

     }

 }

 int main()

 {

     int t;

     char map[][];

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         init();

         for(int i = ; i < n; i++)

         {

             scanf("%s",map[i]);

         }

         for (int i = ; i < n; i++)

         {

             for (int j = ; j < m; j++)

             {

                 if (map[i][j]!='#')

                 {

                     if(i) add((i-)*m+j,i*m+j,,edge1,head1);

                     if(j) add(i*m+j-,i*m+j,,edge1,head1);

                     if (map[i][j]=='*')

                     {

                         int x,y;

                         scanf("%d%d",&x,&y);

                         if(map[x][y]!='#')

                             add(i*m+j,x*m+y,,edge1,head1);

                     }

                 }

             }

         }

         for (int i = ; i < n; i++)

         {

             if (!dfn[i])

                 Tarjan(i);

         }

         for (int i = ; i < n; i++)

         {

             for (int j = ; j < m; j++)

             {

                 if(map[i][j]!='*'&&map[i][j]!='#')

                 {

                     int num = sccno[i*m+j];

                     val[num]+=map[i][j]-'';//记录每个连通分量的价值

                 }

             }

         }

         for (int u = ; u < n*m; u++)

         {

             for (int j = head1[u]; j!=-; j=edge1[j].next)

             {

                 int v = edge1[j].v;

                 if(sccno[u]!=sccno[v])

                 {

                     add(sccno[u],sccno[v],val[sccno[v]],edge2,head2);

                 }//对缩点后的连通分量建立有向图

             }

         }

         spfa(sccno[]);//求出每个点到起始点的价值

         int max=-;

         for (int i = ; i <= scc_cnt; i++)

         {

             if (max < dis[i])

                 max = dis[i];//求出到原点的最大价值

         }

         int ans = max+val[sccno[]];//总最大价值=到原点的最大价值+原点的价值

         printf("%d\n",ans);

     }

     return ;

 }