#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <limits>
#include <list>
#include <numeric>
#include <queue>
#include <stack>
#include <utility>
#include <array>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;
typedef long long ll;
#define dump(x) // // cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl;
// vector出力
template < typename T >
ostream& operator<<(ostream& os, vector< T >& v) {
    os << "{";
    for (int i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i < v.size() - 1 ? ", " : "");
    }
    os << "}";
    return os;
}
// pair出力
template < typename T, typename U >
ostream& operator<<(ostream& os, const pair< T, U >& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// map出力
template < typename T, typename U >
ostream& operator<<(ostream& os, const map< T, U >& map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template < typename T >
ostream& operator<<(ostream& os, const set< T >& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// multiset 出力
template < typename T >
ostream& operator<<(ostream& os, const multiset< T >& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#pragma endregion

/////////////////////////////////////////

int main() {
    ll n;cin >> n;
    ll ans = n;
    set<ll> st;
    for (ll i = 2; i*i <= n; i++) {
        for (ll j = i*i; j <= n; j*=i) {
            if (st.find(j) != st.end()) continue;
            // cout << i << " " << j << endl;
            ans--;
            st.insert(j);
        }
    }
    cout << ans << endl;
    return 0;
}

/////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <complex>
#include <regex>

#define Debug cout << "line: " << __LINE__ << "Debug" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;
#define ALL(a) (a).begin(), (a).end()
#define MP make_pair
#define MOD 1000000007
#define PI 3.14159265358979323846

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vd = vector<double>;
using vl = vector<long long>;

void set_FPD(int n){
    cout << fixed << setprecision(n);
    return;
}

ll Pow(ll a,ll b){
    ll ans=1;
    for(int i=0;i<b;i++) ans*=a;
    return ans;
}

ll apc(ll n,ll b){
    ll ans=0,tmp=pow(2,b);
    ans+=n%tmp;
    ans+=n/tmp;
    return ans;
}

void Main(){
    ll n;
    cin>>n;
    ll m=1e18;
    for(ll b=0;b<64;b++){
        ll tmp=apc(n,b);
        m=min(m,tmp+b);
    }
    cout<<m<<endl;
    return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    Main();
    return 0;
}