#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define all(c) (c).begin(), (c).end() #define zero(a) memset(a, 0, sizeof a) #define minus(a) memset(a, -1, sizeof a) #define minimize(a, x) a = std::min(a, x) #define maximize(a, x) a = std::max(a, x) typedef long long ll; int const inf = 1<<29; typedef __int128_t INT; INT N; INT pow(INT x, INT n, INT M){ INT tmp = 1; if ( n > 0 ){ tmp = pow(x, n/2, M); if ( n%2 == 0 ) tmp = (tmp*tmp)%M; else tmp = (((tmp*tmp)%M)*x)%M; } return tmp; } bool is_prime(INT const& x) { if(x == 2) { return 1; } if(x < 2 || (x%2 == 0)) { return 0; } return pow(2, x-1, x) == 1; } map mp = { {4,3}, {6,5}, {8,7}, {9,7}, {10,7}, {12,11}, {14,13}, {15,7}, {16,7}, {18,8}, {20,19}, {21,19}, {22,7}, {24,23}, }; int main() { string s; cin >> s; INT N = 0; rep(i, s.size()) { N *= 10; N += s[i] - '0'; } if(mp.find(N) != mp.end()) { cout << mp[N] << endl; exit(0); } cout << 8 << endl; return 0; }