#include <iostream>
using namespace std;

int solve(int N) {
    if (N == 1) return 0;
    if (__builtin_popcount(N) == 1) return 1;
    if (N % 2) return 2;
    return 3;
}

int main() {
    int N;
    cin >> N;
    cout << solve(N) << endl;
}