#include<bits/stdc++.h> using namespace std; int n,x,y,z,a,b,c,minn,maxn,i,j,k,l,m,f; bool check(int s){ if(s==0||s==1) return 0; if(s==2) return 1; if(s%2==0) return 0; for(int i=3;i*i<=s;i++){ if(s%i==0) return 0; } return 1; } int hw(int w,int s,int t){ return w/(int)pow(10,s)*(int)pow(10,s)+t*(int)pow(10,s-1)+w%(int)pow(10,s-1); } int main(){ cin>>n; for(i=0;i<=10;i++){ if(i%2!=0){ if(n/10000>=5) x=n/10000-(i+1)/2; else x=n/10000+(i+1)/2; }else{ if(n/10000>=5){ f=n/10000+10; x=(f+(i+1)/2)%10; }else{ f=n/10000+10; x=(f-(i+1)/2)%10; } } y=hw(n,5,x); for(j=0;j<=10;j++){ if(j%2!=0){ if(y/1000%10>=5) x=y/1000%10-(j+1)/2; else x=y/1000%10+(j+1)/2; }else{ if(y/1000%10>=5){ f=y/1000%10+10; x=(f+(j+1)/2)%10; }else{ f=y/1000%10+10; x=(f-(j+1)/2)%10; } } z=hw(y,4,x); for(k=0;k<=10;k++){ if(k%2!=0){ if(z/100%10>=5) x=z/100%10-(k+1)/2; else x=z/100%10+(k+1)/2; }else{ if(z/100%10>=5){ f=z/100%10+10; x=(f+(k+1)/2)%10; }else{ f=z/100%10+10; x=(f-(k+1)/2)%10; } } a=hw(z,3,x); for(l=0;l<=10;l++){ if(l%2!=0){ if(a/10%10>=5) x=a/10%10-(l+1)/2; else x=a/10%10+(l+1)/2; }else{ if(a/10%10>=5){ f=a/10%10+10; x=(f+(l+1)/2)%10; }else{ f=a/10%10+10; x=(f-(l+1)/2)%10; } } b=hw(a,2,x); for(m=0;m<=10;m++){ if(m%2!=0){ if(b/1%10>=5) x=b/1%10-(m+1)/2; else x=b/1%10+(m+1)/2; }else{ if(b/1%10>=5){ f=b/1%10+10; x=(f+(m+1)/2)%10; }else{ f=b/1%10+10; x=(f-(m+1)/2)%10; } } c=hw(b,1,x); if(check(c)&&(minn==0||(i+1)/2+(j+1)/2+(k+1)/2+(l+1)/2+(m+1)/2<minn||(minn==(i+1)/2+(j+1)/2+(k+1)/2+(l+1)/2+(m+1)/2&&c>maxn))){ maxn=c; minn=(i+1)/2+(j+1)/2+(k+1)/2+(l+1)/2+(m+1)/2; } } } } } } printf("%05d",maxn); return 0; }