Birlər

that was so tasty //CrazzyCat

int main() { int n; cin >> n;

vector<int> vec(n + 1);
vec[1] = 1;

for (int i = 2; i <= n; ++i) {
    vec[i] = i;
    for (int j = 1; 2 * j < i; ++j)
        if (vec[j] + vec[i - j] < vec[i])
            vec[i] = vec[j] + vec[i - j];

    for (int j = 2; j * j <= i; ++j)
        if (i % j == 0)
            if (vec[j] + vec[i / j] < vec[i])
                vec[i] = vec[j] + vec[i / j];
}

cout << vec[n] << endl;

return 0;

}