#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(int i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define MOD 1000000007 int isPrime(int n){ int i; if(n < 2){ return 0; } else if(n == 2){ return 1; } if(n % 2 == 0){ return 0; } for(i = 3; i * i <= n; i += 2){ if(n % i == 0){ return 0; } } return 1; } int d[10000][30]; int main(){ long long n; cin>>n; int d[100] = { -1,-1,-1,-1,3,-1,5,-1,7,7,7, -1,11,-1,13,7,7,-1,8,-1,19, 19,7,-1,23,23,8,8,8,-1,8, -1,8,8,8,8,8,-1,8,8,8, -1,8,-1,8,8,8,-1,8,14,8, 8,8,-1,8,8,8,8,8,-1,8, -1,8,8,8,8,8,-1,8,8,8, -1,8,-1,8,8,8,8,8,-1,8, 14,8,-1,8,8,8,8,8,-1,8, 8,8,8,8,8,8,-1,8,8}; if(n<100){ cout << d[n] << endl; return 0; } long long a = n-1; long long b = n-8; if(a%8==0){ rep(i,2,1000000){ if(isPrime(i)==1){ if(b%i==0){ cout << "8" << endl; return 0; } } } cout << "14" << endl; return 0; } else{ cout << "8" << endl; } return 0; }