/*

这题实在调糊了 借鉴的题解的一些判断方法 位运算大法好 - -

因为要集齐所有的宝石所以状态压缩一下

f[i][j][s]将s化为二进制 每一0表示该宝石没有 1表示该宝石有

有：到（i,j）这个点时 宝石收集状况为s的状态是否存在

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int T,n,m,k,f[][][],sx,sy,ex,ey,num;

int xx[]={,,,,-};

int yy[]={,,-,,};

char s[][];

struct point

{

    int mx, my, step, sum;

    point (int xx, int yy, int tt, int ss):mx(xx), my(yy), step(tt), sum(ss){};

};

struct door

{

    int xi, yi;

}door[];

bool check(int s)

{

    int cnt=;

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

      if((s>>i)&==)

        cnt++;

    return(cnt>=k);

}

int main()

{

    scanf("%d",&T);

    while(T--)

      {

          memset(f,,sizeof(f));

          memset(s,,sizeof(s));

          num=;

          queue<point> q;

          int falg=;

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

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

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

              {

                cin>>s[i][j];

                if(s[i][j]=='S')

                  {

                    s[i][j]='.';

                    sx=i;

                  sy=j;

                }

              if(s[i][j]=='E')

                  {

                    s[i][j]='.';

                    ex=i;

                  ey=j;

                }

              if(s[i][j]=='$')

                {

                  num++;

                  door[num].xi=i;

                  door[num].yi=j;

                }

            }

          q.push(point(sx,sy,,));

          f[sx][sy][]=;//初始状态存在

          while(!q.empty())

            {

                point tmmp=q.front();

                q.pop();

                int nx=tmmp.mx;

                int ny=tmmp.my;

                int su=tmmp.sum;

                int time=tmmp.step;

                if(nx==ex&&ny==ey&&check(su))//判断是否符合条件了

                  {

                      printf("%d\n",tmmp.step);

                      falg=;//多组数据害死人啊  一开始return 0 了

              }

            if(falg)break;

            if(s[nx][ny]=='.')//一般的情况 直接周围的点入队

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

                {

                    int ox=nx+xx[i];

                    int oy=ny+yy[i];

                    if(ox>&&ox<=n&&oy>&&oy<=m&&f[ox][oy][su]==&&s[ox][oy]!='#')

                      {

                          f[ox][oy][su]=;

                          q.push(point(ox,oy,time+,su));

                      }

                }

            if(s[nx][ny]=='$')//传送门 把所有传送门周围的点都入队

              {

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

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

                        {

                          int ox=door[i].xi+xx[j];

                        int oy=door[i].yi+yy[j];

                        if(ox>&&ox<=n&&oy>&&oy<=m&&f[ox][oy][su]==&&s[ox][oy]!='#')

                          {

                            f[ox][oy][su]=;

                            q.push(point(ox,oy,time+,su));

                        }

                    }

              }

            if(s[nx][ny]>=''&&s[nx][ny]<='')//开始收集宝石了

                {

                  int si=su|(<< (s[nx][ny]-''));//转化出新状态

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

                    {

                      int ox=nx+xx[i];

                      int oy=ny+yy[i];

                      if(ox>&&ox<=n&&oy>&&oy<=m&&f[ox][oy][si]==&&s[ox][oy]!='#')

                        {

                          f[ox][oy][si]=;

                          q.push(point(ox,oy,time+,si));

                        }

                    }

                }

          }

        if(!falg)

          printf("oop!\n");

      }

    return ;

}