#include<bits/stdc++.h> using namespace std; int n,x,y,z,a,b,c,minn,maxn,i,j,k,l,m; 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(n/10000>=5) x=n/10000-i/2; else x=n/10000+i/2; if(i%2==0) y=hw(n,5,x); else y=hw(n,5,10-x); for(j=0;j<=10;j++){ if(y/1000%10>=5) x=y/1000%10-j/2; else x=y/1000%10+j/2; if(j%2==0) z=hw(y,4,x); else z=hw(y,4,10-x); for(k=0;k<=10;k++){ if(z/100%10>=5) x=z/100%10-k/2; else x=z/100%10+k/2; if(k%2==0) a=hw(z,3,x); else a=hw(z,3,10-x); for(l=0;l<=10;l++){ if(a/10%10>=5) x=a/10%10-l/2; else x=a/10%10+l/2; if(l%2==0) b=hw(a,2,x); else b=hw(a,2,10-x); for(m=0;m<=10;m++){ if(b/1%10>=5) x=b/1%10-m/2; else x=b/1%10+m/2; if(m%2==0) c=hw(b,1,x); else c=hw(b,1,10-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; }