#include <algorithm>
#include <bitset>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

const int N = 10, N2 = 100;
const int NFAC = 4e6;
const int INF = 100;

using B = bitset<N2>;

B permuted_edges[NFAC];

int og[N][N];
int ord[N];
int n;

int cz[N];
bool find_cycle(int i, int d, B pos) {
    if (d == n) return i == 0;
    if (cz[i]) return false;
    cz[i] = 1;
    for (int j = 0; j < n; ++j) {
        if (pos[i*n+j] && !pos[j*n+i] && find_cycle(j, d+1, pos)) {
            cz[i] = 0;
            return true;
        }
    }
    cz[i] = 0;
    return false;
}

struct Query {
    int a, b, dir;
};
vector<Query> qs;
int qz[N][N];

long nstate = 0;

unordered_map<unsigned long, int> cache;

int f(int fuel) {
    long state = nstate++;
    if (state % 100000 == 0) cout << state << endl;
    // Check if Hamiltonian cycle is known
    for (int i = 0; i < n; ++i) ord[i] = i;
    B possible_edges{};
    int pc = 0;
    do {
        bool opos = 1;
        for (auto q : qs) {
            if (og[ord[q.a]][ord[q.b]] != q.dir) {
                opos = 0;
                break;
            }
        }
        if (opos) possible_edges |= permuted_edges[pc];
        pc++;
    } while (next_permutation(ord+1, ord+n)); // XXX: 0 is fixed, not valid with all graphs

    // sanity check
    bool pos = 1;
    for (int i = 0; i < n; ++i) {
        int indeg = 0, outdeg = 0;
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            if (possible_edges[i*n+j] && possible_edges[j*n+i]) continue;
            if (possible_edges[i*n+j]) outdeg++;
            if (possible_edges[j*n+i]) indeg++;
        }
        if (!indeg || !outdeg) {
            pos = 0; break;
        }
    }

    if (pos && find_cycle(0, 0, possible_edges)) {
        return 0;
    }

    if (fuel == 0) return INF;

    int maxn = -1;
    for (auto q : qs) maxn = max({maxn, q.a, q.b});
    maxn += 2;
    maxn = min(maxn, n-1);
    int res = INF;
    int opta = -1, optb = -1;
    int optl = -1, optr = -1;
    for (int a = 0; a <= maxn; ++a) {
        for (int b = a+1; b <= maxn; ++b) {
            if (!possible_edges[a*n+b] || !possible_edges[b*n+a]) continue;
            qs.push_back({a, b, 0});
            int lstate, rstate;
            lstate = nstate;
            int lres = f(min(res, fuel-1));
            int rres, ores;
            if (lres >= res) {
                qs.pop_back();
                continue;
            }
            qs.back().dir = 1;
            rstate = nstate;
            rres = f(min(res, fuel-1));
            ores = max(lres, rres);
            if (ores < res) {
                res = ores;
                opta = a; optb = b;
                optl = lstate; optr = rstate;
            }
            qs.pop_back();
        }
    }
    // if (res < INF) {
    //     cout << state << ": ? " << opta << " " << optb << " -> " << optl << " " << optr << " (" << res << ")" << endl;
    // }
    res++;
    return res;
}

int main() {
    cin >> n;

    // "Circle" graph
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            og[i][j] = i != j && (j > i) != (abs(j-i) <= n/2);
        }
    }

    // Three groups
    // int gs1 = (n + 2) / 3, gs2 = (n + 1) / 3, gs3 = n / 3;
    // auto get_group = [=](int x) {
    //   if (x <= gs1) return 1;
    //   if (x <= gs1+gs2) return 2;
    //   return 3;
    // };

    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 1; j <= n; ++j) {
    //         int ig = get_group(i);
    //         int jg = get_group(j);
    //         bool f;
    //         if (ig != jg) {
    //             // 1 -> 2, 2 -> 3, 3 -> 1
    //             f = (ig == 1 && jg == 2) || (ig == 2 && jg == 3) || (ig == 3 && jg == 1);
    //         } else {
    //             f = i < j;
    //         }
    //         og[i-1][j-1] = f;
    //     }
    // }

    for (int i = 0; i < n; ++i) ord[i] = i;
    int pc = 0;
    do {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                permuted_edges[pc][i*n+j] = og[ord[i]][ord[j]];
            }
        }
        pc++;
    } while (next_permutation(ord, ord+n));

    int res = f(n+1);
    cout << res << endl;
}
