#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
int p[9974],a,b,t[4],f[9974];
struct node
{int n,s;};
void init()
{int i,j;
for(i=1009;i<9974;i++)
{for(j=2;j<=sqrt((double)i);j++)
if(i%j==0)
break;
if(j>sqrt(double(i)))
p[i]=i;
}
}
int bfs()
{queue<node> q;
node st={a,0};
f[a]=1;
q.push(st);
while(!q.empty())
{node ct=q.front();
q.pop();
int temp=ct.n,i=0,j,n,k=1;
while(temp)
{t[i++]=temp%10;
temp/=10;
}
for(j=0;j<4;j++,k*=10)//对应数字的四个位置
for(i=0;i<=9;i++)//分别替换成0到9的数字,判断生成的数字是否是素数,是否已存在,是否是目标数
{
n=ct.n-t[j]*k+i*k;
if(n==b)
return ct.s+1;
if(n!=ct.n&&p[n]&&!f[n])
{f[n]=1;
node ad={n,ct.s+1};
q.push(ad);
}
}
}
}
int main()
{init();
int c;
//scanf("%d",&c);
while(scanf("%d%d",&a,&b)==2
)
{memset(f,0,sizeof(f));
if(a==b)
puts("0");
else
printf("%d\n",bfs());
}
}