Problem: You are working as an analyst in a company working on a new system for big data storage. This system will store n different objects. Each object should have a unique ID.

To create the system, you choose the parameters of the system — integers m ≥ 1 and b_{1}, b_{2}, …, b_{m}. With these parameters an ID of some object in the system is an array of integers [a_{1}, a_{2}, …, a_{m}] where 1 ≤ a_{i} ≤ b_{i} holds for every 1 ≤ i ≤ m.

Developers say that production costs are proportional to ∑_{i=1}^{m} b_{i}. You are asked to choose parameters m and b_{i} so that the system will be able to assign unique IDs to n different objects and production costs are minimized. Note that you don't have to use all available IDs.

Input

In the only line of input there is one positive integer n. The length of the decimal representation of n is no greater than 1.5 ⋅ 10^{6}. The integer does not contain leading zeros.

Output

Print one number — minimal value of ∑_{i=1}^{m} b_{i}.

Examples

Input

36


Output

10


Input

37


Output

11


Input

12345678901234567890123456789


Output

177

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}
template <typename T>
inline istream& operator>>(istream& i, vector<T>& v) {
  for (int j = 0; j < ((int)(v).size()); ++j) i >> v[j];
  return i;
}
template <typename T>
string join(const vector<T>& v) {
  stringstream s;
  for (int i = 0; i < ((int)(v).size()); ++i) s << ' ' << v[i];
  return s.str().substr(1);
}
template <typename T>
inline ostream& operator<<(ostream& o, const vector<T>& v) {
  if ((int)(v).size()) o << join(v);
  return o;
}
template <typename T1, typename T2>
inline istream& operator>>(istream& i, pair<T1, T2>& v) {
  return i >> v.first >> v.second;
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& o, const pair<T1, T2>& v) {
  return o << v.first << "," << v.second;
}
template <typename T>
inline long long int suma(const vector<T>& a) {
  long long int res(0);
  for (auto&& x : a) res += x;
  return res;
}
const double eps = 1e-10;
const long long int LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
const int B = 9;
inline long long int ten(int n) { return n ? ten(n - 1) * 10 : 1; }
const int BS = ten(B);
struct bint;
istream& operator>>(istream& i, bint& a);
ostream& operator<<(ostream& o, const bint& a);
struct bint {
  vector<int> d;
  bool sg;
  bint(long long int n = 0) {
    sg = n < 0;
    if (sg) n = -n;
    while (n) {
      d.push_back(n % BS);
      n /= BS;
    }
  }
  bint(const string& s) {
    sg = s[0] == '-';
    int si = sg;
    for (int i = (int)(s).size(); i > si; i -= B) {
      d.push_back(0);
      for (int j = max(si, i - B); j < i; ++j)
        d.back() = d.back() * 10 + (s[j] - '0');
    }
    cut();
  }
  bint(const vector<int>& d, bool sg = false) : d(d), sg(sg) {}
  inline bint& cut() {
    while ((int)(d).size() && !d.back()) d.pop_back();
    sg &= !iszero();
    return *this;
  }
  inline int size() const { return (int)(d).size(); }
  inline int& operator[](int i) { return d[i]; }
  inline const int& operator[](int i) const { return d[i]; }
  bint abs() const {
    bint a(*this);
    a.sg = false;
    return a;
  }
  inline bool iszero() const { return !(int)(d).size(); }
  bint& _add(const bint& a) {
    if ((int)(d).size() <= (int)(a).size())
      d.resize((int)(a).size() + 1);
    else
      d.push_back(0);
    int i = 0;
    while (i < (int)(a).size()) {
      d[i] += a[i];
      if (d[i] >= BS)
        d[i] -= BS, ++d[++i];
      else
        ++i;
    }
    while (d[i] == BS) d[i] = 0, ++d[++i];
    if (!d.back()) d.pop_back();
    return *this;
  }
  bint& _asub(const bint& a) {
    int i = 0;
    while (i < (int)(a).size()) {
      d[i] -= a[i];
      if (d[i] < 0)
        d[i] += BS, --d[++i];
      else
        ++i;
    }
    if (i < (int)(d).size())
      while (d[i] == -1) d[i] = BS - 1, --d[++i];
    return cut();
  }
  bint& _sub(const bint& a) {
    if (_cmp(a)) {
      bint b(a);
      swap(*this, b);
      return _asub(b);
    }
    return _asub(a);
  }
  bint& operator+=(const bint& a) {
    if (sg == a.sg) return _add(a);
    return _sub(a);
  }
  bint& operator-=(const bint& a) {
    if (sg != a.sg) return _add(a);
    sg ^= 1;
    _sub(a);
    if (!iszero()) sg ^= 1;
    return *this;
  }
  bint& operator*=(long long int a) {
    if (!a) return *this = 0;
    if (a < 0) sg ^= 1, a = -a;
    long long int x = 0;
    for (int i = 0; i < ((int)(d).size()); ++i) {
      x += a * d[i];
      d[i] = x % BS;
      x /= BS;
    }
    while (x) d.push_back(x % BS), x /= BS;
    return *this;
  }
  bint mult(const bint& a) const {
    if (a.iszero()) return 0;
    bint b = (*this) * a.d.back();
    b.sg ^= a.sg;
    for (int i = ((int)(a).size() - 1) - 1; i >= 0; --i) {
      b.d.insert(b.d.begin(), 0);
      b += (*this) * a[i];
    }
    return b;
  }
  int operator%(int a) const {
    assert(a > 0);
    long long int r = 0;
    for (int i = ((int)(d).size()) - 1; i >= 0; --i) r = (r * BS + d[i]) % a;
    if (sg) r = (a - r) % a;
    return r;
  }
  bint& operator/=(int a) {
    assert(a);
    if (a < 0) sg ^= 1, a = -a;
    long long int x = 0;
    for (int i = ((int)(d).size()) - 1; i >= 0; --i) {
      x = x * BS + d[i];
      d[i] = x / a;
      x %= a;
    }
    return cut();
  }
  bint operator+(const bint& a) const { return bint(*this) += a; }
  bint operator-(const bint& a) const { return bint(*this) -= a; }
  bint operator*(long long int a) const { return bint(*this) *= a; }
  bint& operator*=(int a) { return (*this) *= (long long int)a; }
  bint operator*(int a) const { return bint(*this) *= (long long int)a; }
  bint operator*(const bint& a) const;
  bint& operator*=(const bint& a) { return *this = (*this) * a; }
  bint operator/(int a) const { return bint(*this) /= a; }
  bint operator/(const bint& a) const { return bint(); }
  bint operator%(const bint& a) const { return bint(); }
  bint ex(long long int t) const {
    if (!t) return 1;
    bint a = ex(t >> 1);
    a *= a;
    if (t & 1) return a * (*this);
    return a;
  }
  bool _cmp(const bint& a) const {
    if ((int)(d).size() != (int)(a).size())
      return (int)(d).size() < (int)(a).size();
    for (int i = ((int)(d).size()) - 1; i >= 0; --i)
      if (d[i] != a[i]) return d[i] < a[i];
    return false;
  }
  bool operator<(const bint& a) const {
    if (sg != a.sg) return sg;
    return sg ? a._cmp(*this) : _cmp(a);
  }
  bool operator<=(const bint& a) const { return !(a < (*this)); }
  bool operator==(const bint& a) const { return sg == a.sg && d == a.d; }
  string str() const {
    if (!(int)(d).size()) return "0";
    ostringstream os;
    if (sg) os << '-';
    os << d.back();
    for (int i = ((int)(d).size() - 1) - 1; i >= 0; --i)
      os << setw(B) << setfill('0') << d[i];
    return os.str();
  }
};
long long int extgcd(long long int a, long long int b, long long int& x,
                     long long int& y) {
  for (long long int u = y = 1, v = x = 0; a;) {
    long long int q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
long long int mod_inv(long long int a, long long int m) {
  long long int x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
long long int mod_pow(long long int a, long long int n, long long int mod) {
  long long int ret = 1;
  long long int p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
template <int mod, int primitive_root>
struct NTT {
  int get_mod() const { return mod; }
  void _ntt(vector<int>& a, int sign) {
    const int n = (int)(a).size();
    int h = mod_pow(primitive_root, (mod - 1) / n, mod);
    if (sign == -1) h = mod_inv(h, mod);
    int i = 0;
    for (int j = 1; j < n - 1; ++j) {
      for (int k = n >> 1; k > (i ^= k); k >>= 1)
        ;
      if (j < i) swap(a[i], a[j]);
    }
    for (int m = 1; m < n; m *= 2) {
      const int m2 = m * 2;
      const long long int base = mod_pow(h, n / m2, mod);
      long long int w = 1;
      for (int x = 0; x < (m); ++x) {
        for (int s = x; s < n; s += m2) {
          long long int d = a[s + m] * w % mod;
          a[s + m] = a[s] - d;
          if (a[s + m] < 0) a[s + m] += mod;
          d += a[s];
          if (d >= mod) d -= mod;
          a[s] = d;
        }
        w = w * base % mod;
      }
    }
  }
  void ntt(vector<int>& input) { _ntt(input, 1); }
  void intt(vector<int>& input) {
    _ntt(input, -1);
    const int n_inv = mod_inv((int)(input).size(), mod);
    for (auto& x : input) x = (long long int)x * n_inv % mod;
  }
  vector<int> convolution(const vector<int>& a, const vector<int>& b) {
    int ntt_size = 1;
    while (ntt_size < (int)(a).size() + (int)(b).size()) ntt_size *= 2;
    vector<int> _a = a, _b = b;
    _a.resize(ntt_size);
    _b.resize(ntt_size);
    ntt(_a);
    ntt(_b);
    for (int i = 0; i < (ntt_size); ++i)
      _a[i] = (long long int)_a[i] * _b[i] % mod;
    intt(_a);
    return _a;
  }
};
const int P1 = 1811939329;
const int P2 = 2013265921;
const int P3 = 2113929217;
const long long int P12 = (long long int)P1 * P2;
const int IP1_2 = mod_inv(P1, P2);
const int IP12_3 = mod_inv(P12, P3);
const long long int P12_R = P12 % BS;
const long long int P12_Q = P12 / BS;
bint bint::operator*(const bint& a) const {
  NTT<P1, 13> ntt1;
  NTT<P2, 31> ntt2;
  NTT<P3, 5> ntt3;
  vector<int> x = ntt1.convolution(d, a.d);
  vector<int> y = ntt2.convolution(d, a.d);
  vector<int> z = ntt3.convolution(d, a.d);
  long long int c = 0;
  for (int i = 0; i < ((int)(x).size()); ++i) {
    y[i] = ((long long int)y[i] - x[i] + P2) * IP1_2 % P2;
    long long int s = x[i] + (long long int)y[i] * P1;
    z[i] = (z[i] - s % P3 + P3) * IP12_3 % P3;
    s += c + P12_R * z[i];
    c = P12_Q * z[i] + s / BS;
    x[i] = s % BS;
  }
  return bint(x, sg ^ a.sg).cut();
}
istream& operator>>(istream& i, bint& a) {
  string s;
  i >> s;
  a = bint(s);
  return i;
}
ostream& operator<<(ostream& o, const bint& a) { return o << a.str(); }
bint n;
double ln;
void init() {
  double dn = 0;
  for (int i = 0; i < ((int)(n).size()); ++i) dn = dn / BS + n[i];
  ln = log(dn) + log(BS) * ((int)(n).size() - 1);
}
const double l2 = log(2);
const double l3 = log(3);
double fl(int x) {
  if (x % 3) return fl(x - 2) + l2;
  return l3 * (x / 3);
}
bint fb(int x) {
  if (x % 3) return fb(x - 2) * 2;
  return bint(3).ex(x / 3);
}
bool f(int x) {
  double lx = fl(x);
  if (abs(lx - ln) > 1e-1) return ln < lx;
  bint bx = fb(x);
  return n <= bx;
}
int main() {
  cin >> n;
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  init();
  int l = 1, r = 1e7;
  while (l + 1 < r) {
    int c = (l + r) >> 1;
    if (f(c))
      r = c;
    else
      l = c;
  }
  cout << r << endl;
  return 0;
}