#include <bits/stdc++.h>
using namespace std;
#define accelerate ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n";
#define mod 12345
#define ll long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const int N=1e2+10;
ll n,m,k,x,y,T;
ll a[N];
ll pre[N][2];
string ss;
struct node{
	int a,b,c,d,e;
	int now;
}aa;
ll ans=INF,ans1=-1;
bool f(int x){
	if(x==1||x==0) return 0;
	for(int i=2;i*i<=x;i++){
		if(x%i==0) return 0;
	}
	return 1;
}
int mul(int a,int b,int c,int d,int e){return a*10000+b*1000+c*100+d*10+e;}
queue<node>q;
void dfs(){
	q.push(aa);
	while(!q.empty()){
		node e=q.front();q.pop();
		int tt=mul(e.a,e.b,e.c,e.d,e.e);
		if(f(tt)){
			if(e.now<ans){
				ans=e.now;
				ans1=tt;
			}
			else if(e.now==ans&&tt>ans1){
				ans1=tt;
			}
			continue;
		}
		if(e.now>ans) continue;
		q.push(node{(e.a-1+10)%10,e.b,e.c,e.d,e.e,e.now+1});
		q.push(node{(e.a+1)%10,e.b,e.c,e.d,e.e,e.now+1});
		q.push(node{e.a,(e.b-1+10)%10,e.c,e.d,e.e,e.now+1});
		q.push(node{e.a,(e.b+1)%10,e.c,e.d,e.e,e.now+1});
		q.push(node{e.a,e.b,(e.c+1)%10,e.d,e.e,e.now+1});
		q.push(node{e.a,e.b,(e.c-1+10)%10,e.d,e.e,e.now+1});
		q.push(node{e.a,e.b,e.c,(e.d-1+10)%10,e.e,e.now+1});
		q.push(node{e.a,e.b,e.c,(e.d+1)%10,e.e,e.now+1});
		q.push(node{e.a,e.b,e.c,e.d,(e.e-1+10)%10,e.now+1});
		q.push(node{e.a,e.b,e.c,e.d,(e.e+1)%10,e.now+1});
	}
}
int main(){
	//accelerate;
	cin>>ss;
	aa.a=ss[0]-'0',aa.b=ss[1]-'0',aa.c=ss[2]-'0',aa.d=ss[3]-'0',aa.e=ss[4]-'0';
	aa.now=0;
	dfs();
	printf("%05d",ans1);
	return 0;
}