#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct Point{
public:
int x;
int y;
int step;
Point(int setx,int sety,int step);
bool CheckBound(int x, int y);
bool ReachEnd(int endX, int endY);
};
Point::Point( int setx , int sety, int step): x(setx), y(sety), step(step) { //?? what about label[8][8]?
//label[setx][sety]=1;
}
bool Point::CheckBound(int x,int y){
return (x>=0 && x<8 && y>=0 && y<8) ? true:false;
}
//void Point::Expand(int x,int y,int[8][8] label){}
bool Point::ReachEnd(int endX, int endY){
return (x==endX && y==endY)? true:false;
}
int main() {
string startStr,endStr;
while(cin>>startStr>>endStr){
int startX,startY;
int endX,endY;
startX = startStr[0]-\'a\';
startY = startStr[1]-\'1\';
endX = endStr[0]-\'a\';
endY = endStr[1]-\'1\';
int label[8][8]={0};
Point start(startX,startY,0);
Point end(endX,endY,0);
Point temp(0,0,0);
if( start.ReachEnd(endX,endY) ){
cout<<"To get from "<<startStr<<" to "<<endStr<<" takes 0 knight moves."<<endl;
continue;
}
queue<Point> BFS;
const int knight[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
BFS.push(start);
bool find = false;
while(!find){
//initail
temp = BFS.front();
BFS.pop();
label[temp.x][temp.y]=1;
//found end
if(temp.ReachEnd(end.x,end.y)){
cout<<"To get from "<<startStr<<" to "<<endStr<<" takes "<<temp.step<<" knight moves."<<endl;
find = true;
break;
}
//expand
for(int i=0;i<8;i++){
int expandedX = temp.x+knight[i][0];
int expandedY = temp.y+knight[i][1];
if ( temp.CheckBound(expandedX,expandedY) && label[expandedX][expandedY]==0 )
{
label[expandedX][expandedY] = 1;
Point expandedPoint(expandedX,expandedY,temp.step+1);
BFS.push(expandedPoint);
}
}
}
}
return 0;
}