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