#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <vector>
 
using namespace std;
 
int solve(int p,int q) {
	// ある素数からある素数への変換が可能な組を管理するmultimap
    multimap<int,int> pe;
    {
        vector<bool> isprime(q+1,true);
        isprime[0]=false;
        isprime[1]=false;
        // エラトステネスの篩による、q以下の数の素数/非素数判別
        for ( int i=2; i*i<=q; i++ ) {
            if ( isprime[i] ) {
                for ( int j=i*i; j<=q; j+=i ) {
                    isprime[j]=false;
                }
            }
        }
 
        // 変換可能な素数のペアを ( 双方向で ) 登録
        for ( int i=11; i<=q; i+=2 ) {
            if ( isprime[i] ) {
                int irtrim=i/10;
                if ( isprime[irtrim] ) {
                    pe.insert(pair<int,int>(i,irtrim));
                    pe.insert(pair<int,int>(irtrim,i));
                }
                string i_s=to_string(i);
                if ( i_s[1]!='0' ) {
                    int iltrim=stoi(i_s.substr(1));
                    if ( isprime[iltrim] ) {
                        pe.insert(pair<int,int>(i,iltrim));
                        pe.insert(pair<int,int>(iltrim,i));
                    }
                }
            }
        }
    }
 
    // BFS用の、距離・素数のペアのキュー
    queue<pair<int,int>> bfsq;
    // 探索済み素数を登録するmap
    map<int,bool> done;
    done[p]=true;
    // pから開始
    bfsq.push(pair<int,int>(0,p));
    while ( !bfsq.empty() ) {
        auto ip=bfsq.front();
        bfsq.pop();
        int d=ip.first,curp=ip.second;
        auto itp=pe.equal_range(curp);
        for ( auto it=itp.first; it!=itp.second; it++ ) {
            int nextp=it->second;
            // 目的のqに到着
            if ( nextp==q ) {
                return d+1;
            }
            // doneに登録されていない、すなわち未探索の素数の場合
            if ( done.find(nextp)==done.end() ) {
                bfsq.push(pair<int,int>(d+1,nextp));
                done[nextp]=true;
            }
        }
    }
    return -1;
}
 
int main(void) {
    int p,q;
    cin>>p>>q;
    cout<<solve(p,q)<<endl;
}