#include #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rep2(i, a) rep3 (i, 0, a) #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__) #define repr2(i, a) repr3 (i, 0, a) #define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; template inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template T parse(string s) { istringstream iss(s); T res; iss >> res; return res; } bool isprime(ll n) { for (ll i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return n != 1; } bool check(int n, int w) { queue> q; vector> vis(n + 1, vector(w)); q.emplace(0, 0); vis[0][0] = true; n--; while (!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); int dy[] = {0, 1, 0, -1}; int dx[] = {1, 0, -1, 0}; rep (k, 4) { int ny = y + dy[k]; int nx = x + dx[k]; int nv = ny * w + nx; if (ny < 0 || nx < 0 || nx >= w || nv > n) continue; if (isprime(nv + 1)) continue; if (vis[ny][nx]) continue; vis[ny][nx] = true; q.emplace(ny, nx); } } return vis[n / w][n % w]; } int main() { string N; cin >> N; int m = 0; rep (i, N.length()) { m = (m * 10 + (N[i] - '0')) % 6; } if (m == 2 || m == 4) { cout << 6 << endl; } else if (N.length() >= 3) { cout << 8 << endl; } else { int n = parse(N); int ans = 1; while (!check(n, ans)) ans++; cout << ans << endl; } return 0; }