C++ :

#include <bits/stdc++.h>
using namespace std;

//求s1到n要播几次 
int num(string s1,int n){
	 int c = 0;
	 int i = 4;//s1取最后一位 
	 int t;//由小到大拨过去次数 
	 while(n != 0){
	 	t =  abs((n % 10) - (s1[i] - '0'));
	 	if(t <= 10 - t) c = c + t;
		else c = c + 10 - t;
		i--;
	    n = n / 10;
	 } 
	 
	 //剩余的数播回0 
	 for(int j = i;j >= 0;j--){
	 	  if(s1[j] == '9') c++;
		  else c = c + (s1[j] - '0'); 
	 }
	 
	 return c;
}

//素数判断 
bool sushu(int n){
	int i; 
	if(n <= 1) return false;
	for(i = 2;i <= sqrt(n);i++){
		if(n % i == 0){
			return false;
		}
	}
	
	return true;
}



int main(){
	string s;
	cin>>s;
	int i,mi = INT_MAX,x,r; 
	for(i = 2;i <= 99999;i++){
		if(sushu(i)){
			x = num(s,i);
//			cout<<i<<" "<<x<<endl; 
			if(x <= mi){
				mi = x;
				r = i;
			}
		}
	}
	
	//输出r前面补0
	string s2 = "";
	while(r != 0){
		s2 = s2 + (char)(r % 10 + 48);
		r = r / 10;
	} 
	
	
	for(i = 1;i <= 5 - s2.size();i++){
		cout<<0;
	}
	
	for(i = s2.size() - 1;i >= 0;i--){
		cout<<s2[i];
	}
}