#include <iostream>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <memory>

#include <cmath>

#include <bitset>

#include <queue>

#include <vector>

#include <stack>

using namespace std;

#define CLR(x,y) memset(x,y,sizeof(x))

#define MIN(m,v) (m)<(v)?(m):(v)

#define MAX(m,v) (m)>(v)?(m):(v)

#define ABS(x) ((x)>0?(x):-(x))

#define rep(i,x,y) for(i=x;i<y;++i)

#define SET_NODE(no,a,b,c) {no.x=a;no.y=b;no.val=c;}

const int MAXN = 200;

const double INF = 1<<30;

const double EPS = 0.000001;

int dir[4][2]={1,0,-1,0,0,1,0,-1};

int n,m;

int tag[MAXN];

char g[MAXN][MAXN];

double dist;

bool visit[MAXN][MAXN];

double dis[MAXN][MAXN];

typedef struct

{

	int x,y;

	double val;

}Node;

Node s,e,node;

bool operator < (const Node& a,const Node& b)

{

    return a.val > b.val;

}

bool check(const int& x, const int& y)

{

	if(x<0||x>=n) return false;

	if(y<0||y>=m) return false;

	if(g[x][y] == '#') return false;

	if(visit[x][y]) return false;

	return true;

}

double BFS(double len)

{

	int i,j,k;

	Node tmp;

	priority_queue<Node> q;

	q.push(s);

	CLR(visit,0);

	rep(i,0,n)

		rep(j,0,m)

			dis[i][j] = INF;

	while(!q.empty())

	{

		node = q.top();

		q.pop();

		visit[node.x][node.y] = true;

		if(node.x == e.x && node.y == e.y)

			return node.val;

		if(check(node.x+1,node.y)){

			SET_NODE(tmp,node.x+1,node.y,node.val+len);

			if(tmp.val<dis[tmp.x][tmp.y])

			{

				dis[tmp.x][tmp.y] = tmp.val;

				q.push(tmp);

			}

		}

		if(check(node.x-1,node.y)){

			SET_NODE(tmp,node.x-1,node.y,node.val+len);

			if(tmp.val<dis[tmp.x][tmp.y])

			{

				dis[tmp.x][tmp.y] = tmp.val;

				q.push(tmp);

			}

		}

		if(check(node.x,node.y+1)){

			SET_NODE(tmp,node.x,node.y+1,node.val+1);

			if(tmp.val<dis[tmp.x][tmp.y])

			{

				dis[tmp.x][tmp.y] = tmp.val;

				q.push(tmp);

			}

		}

		if(check(node.x,node.y-1)){

			SET_NODE(tmp,node.x,node.y-1,node.val+1);

			if(tmp.val<dis[tmp.x][tmp.y])

			{

				dis[tmp.x][tmp.y] = tmp.val;

				q.push(tmp);

			}

		}

	}

	return 0;

}

void Solve()

{

	int i,j,k,t,tt;

	scanf("%d",&tt);

	rep(t,1,tt+1){

		scanf("%lf%d",&dist,&n);

		rep(i,0,n)

		{

		getchar();

			gets(&g[i][0]);

		}

		m = strlen(g[0]);

		rep(i,0,n)

			rep(j,0,m)

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

				{

					s.x = i;

					s.y = j;

				}else if (g[i][j]=='E')

				{

					e.x = i;

					e.y = j;

				}

		s.val = 0;

		double low = 0;

		double high = 10;

		double mid = (low+high)/2;

		double res = 0;

		while(ABS(low-high)>EPS)

		{

			mid = (low+high)/2;

			res = BFS(mid);

			//printf("[%f %f %f]\n",mid,res,dist);

			if(res < dist+EPS)

				low = mid ;

			else

				high = mid;

		}

		printf("Case #%d: %.3f%%\n",t,mid*100);

	}

}

int main()

{

	Solve();

	return 0;

}