#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

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

    ll r = n + 1;

    for (ll i = 1; i * i < n; i++) {
        if (n % i == 0) {
            ll p = n / i - 1;
            if (i < p) r = min(r, p);
        }
    }

    for (ll p = 2; p * p + p + 1 <= n; p++) {
        ll t = 1;
        do {
            if (n % t == 0 && n / t < p) {
                r = min(r, p);
                break;
            }
            t *= p;
            t += 1;
        } while (t <= n);
    }

    cout << r << endl;

    return 0;
}