//開一個四維數組，前面兩維表示在圖中的位置
//後面兩維表示到達該位置有多少個鑰匙和經過的路線有多少條蛇
//由於時間和步數不同步，所以得用優先隊列來做
//或者遍歷所有情況得到最大值
//由於鑰匙需要按照順序找，所以能直接記錄最後一個鑰匙的大小
//而對於經過蛇不是特定的順序，所以對於蛇的記錄可以運用一個二進制數表示
#include
#include
#include
#include
using namespace std;
const int maxn = 110;
const int inf = 0x7fffffff ;
char map[maxn][maxn];
int vis[maxn][maxn][10][32];
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
int st_x,st_y,en_x,en_y;
int snake[maxn][maxn] ;
int N , M;
//int ans ;
struct node
{
int x,y ;
int state ;
int step;
int key ;
};
int get_num(int a)
{
int ans_a = 0;
int temp_a = a;
while(temp_a){
ans_a += (temp_a%2);
temp_a/=2;
}
return ans_a;
}
struct cmp{
bool operator()(struct node &a,struct node &b){
return a.step+get_num(a.state) > b.step+get_num(b.state);
}
};
int flag = 0;
void bfs()
{
memset(vis,0,sizeof(vis));
priority_queue,cmp> que;
//queueque;
struct node first = {st_x,st_y,0,0,0};
que.push(first);
vis[st_x][st_y][0][0] = 1;
while(que.size())
{
struct node now = que.top();
//struct node now = que.front();
que.pop();
if(now.key == M && now.x == en_x && now.y == en_y)
{
printf("%d\n",now.step+get_num(now.state));
//ans = min(ans,now.step+get_num(now.state));
flag = 1;
break;
}
for(int i = 0;i < 4;i++)
{
struct node next ;
next.x = now.x + dx[i];
next.y= now.y + dy[i];
if(map[next.x][next.y] == '#' || next.x<1 || next.x>N || next.y<1 || next.y > N)
continue ;
if(map[next.x][next.y] == '.' || map[next.x][next.y] == 'K' || map[next.x][next.y] == 'T')
{
next.key = now.key ;
next.state = now.state;
}
else if(map[next.x][next.y] == 'S')
{
if(!((1<
next.state = now.state | (1<
else
next.state = now.state ;
next.key = now.key ;
}
else if(map[next.x][next.y] >= '1' && map[next.x][next.y] <= '9')
{
if(now.key + 1 == (map[next.x][next.y] - '0'))
next.key = map[next.x][next.y] -'0';
else
next.key = now.key ;
next.state = now.state ;
}
if(vis[next.x][next.y][next.key][next.state])
continue;
vis[next.x][next.y][next.key][next.state] = 1;
next.step = now.step + 1;
que.push(next);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&N,&M)&&(N||M))
{
int num_s = 0;
for(int i = 1;i <= N;i++)
{
scanf("%s",&map[i][1]);
for(int j = 1;j <= N;j++)
{
if(map[i][j] == 'S')
snake[i][j] = num_s++;
if(map[i][j] == 'K')
st_x = i , st_y = j;
if(map[i][j] == 'T')
en_x = i , en_y = j;
}
}
// ans = inf ;
flag = 0 ;
bfs();
if(!flag)
printf("impossible\n");
//if(ans == inf)
// printf("impossible\n");
// else
// printf("%d\n",ans);
}
return 0;
}
