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;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
namespace FFT {
const int maxf = 1 << 18;
struct cp {
  long double x, y;
  cp(long double x = 0, long double y = 0) : x(x), y(y) {}
  cp operator+(const cp& rhs) const { return cp(x + rhs.x, y + rhs.y); }
  cp operator-(const cp& rhs) const { return cp(x - rhs.x, y - rhs.y); }
  cp operator*(const cp& rhs) const {
    return cp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
  cp operator!() const { return cp(x, -y); }
} rts[maxf + 1];
cp fa[maxf], fb[maxf];
cp fc[maxf], fd[maxf];
int bitrev[maxf];
void fftinit() {
  int k = 0;
  while ((1 << k) < maxf) k++;
  bitrev[0] = 0;
  for (int i = 1; i < maxf; i++) {
    bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
  }
  long double PI = acos((long double)-1.0);
  rts[0] = rts[maxf] = cp(1, 0);
  for (int i = 1; i + i <= maxf; i++) {
    rts[i] = cp(cos(i * 2 * PI / maxf), sin(i * 2 * PI / maxf));
  }
  for (int i = maxf / 2 + 1; i < maxf; i++) {
    rts[i] = !rts[maxf - i];
  }
}
void dft(cp a[], int n, int sign) {
  static int isinit;
  if (!isinit) {
    isinit = 1;
    fftinit();
  }
  int d = 0;
  while ((1 << d) * n != maxf) d++;
  for (int i = 0; i < n; i++) {
    if (i < (bitrev[i] >> d)) {
      swap(a[i], a[bitrev[i] >> d]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int delta = maxf / len * sign;
    for (int i = 0; i < n; i += len) {
      cp *x = a + i, *y = a + i + (len >> 1), *w = sign > 0 ? rts : rts + maxf;
      for (int k = 0; k + k < len; k++) {
        cp z = *y * *w;
        *y = *x - z, *x = *x + z;
        x++, y++, w += delta;
      }
    }
  }
  if (sign < 0) {
    for (int i = 0; i < n; i++) {
      a[i].x /= n;
      a[i].y /= n;
    }
  }
}
void multiply(int a[], int b[], int na, int nb, long long c[]) {
  int n = na + nb - 1;
  while (n != (n & -n)) n += n & -n;
  for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  for (int i = 0; i < na; i++) fa[i] = cp(a[i]);
  for (int i = 0; i < nb; i++) fb[i] = cp(b[i]);
  dft(fa, n, 1), dft(fb, n, 1);
  for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i];
  dft(fa, n, -1);
  for (int i = 0; i < n; i++) c[i] = (long long)floor(fa[i].x + 0.5);
}
void multiply(int a[], int b[], int na, int nb, int c[], int& nc, int base) {
  int n = na + nb - 1;
  while (n != (n & -n)) n += n & -n;
  for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  static const int magic = 15;
  for (int i = 0; i < na; i++)
    fa[i] = cp(a[i] >> magic, a[i] & (1 << magic) - 1);
  for (int i = 0; i < nb; i++)
    fb[i] = cp(b[i] >> magic, b[i] & (1 << magic) - 1);
  dft(fa, n, 1), dft(fb, n, 1);
  for (int i = 0; i < n; i++) {
    int j = (n - i) % n;
    cp x = fa[i] + !fa[j];
    cp y = fb[i] + !fb[j];
    cp z = !fa[j] - fa[i];
    cp t = !fb[j] - fb[i];
    fc[i] = (x * t + y * z) * cp(0, 0.25);
    fd[i] = x * y * cp(0, 0.25) + z * t * cp(-0.25, 0);
  }
  dft(fc, n, -1), dft(fd, n, -1);
  nc = 0;
  long long carry = 0;
  for (int i = 0; i < n; i++) {
    long long u = (long long)round(fc[i].x);
    long long v = (long long)round(fd[i].x);
    long long w = (long long)round(fd[i].y);
    long long ncarry = (u / base << 15) + (u % base << 15) / base + v / base +
                       (w / base << 30) + (w % base << 30) / base;
    assert(0 <= ncarry && ncarry < 2e18);
    long long t =
        (u % base << 15) % base + v % base + (w % base << 30) % base + carry;
    carry = ncarry + t / base;
    assert(carry < 2e18);
    c[nc++] = t % base;
  }
  while (carry) {
    c[nc++] = carry % base;
    carry /= base;
  }
}
vector<int> multiply(vector<int> a, vector<int> b, int base) {
  static int fa[maxf], fb[maxf], fc[maxf + 5];
  int na = a.size(), nb = b.size();
  for (int i = 0; i < na; i++) fa[i] = a[i];
  for (int i = 0; i < nb; i++) fb[i] = b[i];
  int nc = 0;
  multiply(fa, fb, na, nb, fc, nc, base);
  vector<int> res(nc);
  for (int i = 0; i < nc; i++) res[i] = fc[i];
  while (1 < res.size() && !res.back()) res.pop_back();
  return res;
}
}  // namespace FFT
const int base = 10;
const int nblock = 9;
const int blockbase = (int)round(pow(base, nblock));
struct Bigint {
  vector<int> a;
  int sign;
  Bigint() : sign(1) {}
  Bigint(long long v) { *this = v; }
  Bigint(const string& s) { read(s); }
  void operator=(const Bigint& v) {
    sign = v.sign;
    a = v.a;
  }
  void operator=(long long v) {
    a.clear();
    sign = 1;
    if (v < 0) sign = -1, v = -v;
    for (; v > 0; v = v / blockbase) a.push_back(v % blockbase);
  }
  Bigint operator+(const Bigint& v) const {
    if (sign == v.sign) {
      Bigint res = v;
      for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry;
           i++) {
        if (i == (int)res.a.size()) res.a.push_back(0);
        res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
        carry = res.a[i] >= blockbase;
        if (carry) res.a[i] -= blockbase;
      }
      return res;
    }
    return *this - (-v);
  }
  Bigint operator-(const Bigint& v) const {
    if (sign == v.sign) {
      if (abs() >= v.abs()) {
        Bigint res = *this;
        for (int i = 0, carry = 0; i < (int)v.a.size() || carry; i++) {
          res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
          carry = res.a[i] < 0;
          if (carry) res.a[i] += blockbase;
        }
        res.trim();
        return res;
      }
      return -(v - *this);
    }
    return *this + (-v);
  }
  void operator*=(int v) {
    if (v < 0) sign = -sign, v = -v;
    for (int i = 0, carry = 0; i < (int)a.size() || carry; i++) {
      if (i == (int)a.size()) a.push_back(0);
      long long cur = a[i] * (long long)v + carry;
      carry = (int)(cur / blockbase);
      a[i] = (int)(cur % blockbase);
    }
    trim();
  }
  void operator*=(long long v) {
    if (v >= (long long)blockbase * blockbase) {
      *this *= Bigint(v);
    }
    int a = v / blockbase;
    int b = v % blockbase;
    *this = *this * a * blockbase + *this * b;
  }
  Bigint operator*(int v) const {
    Bigint res = *this;
    res *= v;
    return res;
  }
  Bigint operator*(long long v) const {
    Bigint res = *this;
    res *= v;
    return res;
  }
  friend pair<Bigint, Bigint> divmod(const Bigint& a1, const Bigint& b1) {
    int norm = blockbase / (b1.a.back() + 1);
    Bigint a = a1.abs() * norm;
    Bigint b = b1.abs() * norm;
    Bigint q, r;
    q.a.resize(a.a.size());
    for (int i = a.a.size() - 1; i >= 0; i--) {
      r *= blockbase;
      r += a.a[i];
      int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
      int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
      int d = ((long long)blockbase * s1 + s2) / b.a.back();
      r -= b * d;
      while (r < 0) r += b, d--;
      q.a[i] = d;
    }
    q.sign = a1.sign * b1.sign;
    r.sign = a1.sign;
    q.trim();
    r.trim();
    return make_pair(q, r / norm);
  }
  Bigint operator/(const Bigint& v) const { return divmod(*this, v).first; }
  Bigint operator%(const Bigint& v) const { return divmod(*this, v).second; }
  void operator/=(int v) {
    if (v < 0) sign = -sign, v = -v;
    for (int i = (int)a.size() - 1, rem = 0; i >= 0; i--) {
      long long cur = a[i] + rem * (long long)blockbase;
      a[i] = (int)(cur / v);
      rem = (int)(cur % v);
    }
    trim();
  }
  void operator/=(long long v) { *this /= Bigint(v); }
  Bigint operator/(int v) const {
    Bigint res = *this;
    res /= v;
    return res;
  }
  Bigint operator/(long long v) const {
    Bigint res = *this;
    res /= v;
    return res;
  }
  int operator%(int v) const {
    if (v < 0) v = -v;
    int m = 0;
    for (int i = a.size() - 1; i >= 0; i--)
      m = (a[i] + m * (long long)blockbase) % v;
    return m * sign;
  }
  long long operator%(long long v) const {
    return (*this % Bigint(v)).longValue();
  }
  void operator+=(const Bigint& v) { *this = *this + v; }
  void operator-=(const Bigint& v) { *this = *this - v; }
  void operator*=(const Bigint& v) { *this = *this * v; }
  void operator/=(const Bigint& v) { *this = *this / v; }
  bool operator<(const Bigint& v) const {
    if (sign != v.sign) return sign < v.sign;
    if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
    for (int i = a.size() - 1; i >= 0; i--)
      if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign;
    return false;
  }
  bool operator>(const Bigint& v) const { return v < *this; }
  bool operator<=(const Bigint& v) const { return !(v < *this); }
  bool operator>=(const Bigint& v) const { return !(*this < v); }
  bool operator==(const Bigint& v) const {
    return !(*this < v) && !(v < *this);
  }
  bool operator!=(const Bigint& v) const { return *this < v || v < *this; }
  void trim() {
    while (!a.empty() && !a.back()) a.pop_back();
    if (a.empty()) sign = 1;
  }
  bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); }
  Bigint operator-() const {
    Bigint res = *this;
    res.sign = -sign;
    return res;
  }
  Bigint abs() const {
    Bigint res = *this;
    res.sign *= res.sign;
    return res;
  }
  long long longValue() const {
    long long res = 0;
    for (int i = a.size() - 1; i >= 0; i--) res = res * blockbase + a[i];
    return res * sign;
  }
  friend Bigint gcd(const Bigint& a, const Bigint& b) {
    return b.isZero() ? a : gcd(b, a % b);
  }
  friend Bigint lcm(const Bigint& a, const Bigint& b) {
    return a / gcd(a, b) * b;
  }
  void read(const string& s) {
    sign = 1;
    a.clear();
    int pos = 0;
    while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
      if (s[pos] == '-') sign = -sign;
      pos++;
    }
    for (int i = s.size() - 1; i >= pos; i -= nblock) {
      int x = 0;
      for (int j = max(pos, i - nblock + 1); j <= i; j++)
        x = x * base + s[j] - '0';
      a.push_back(x);
    }
    trim();
  }
  friend istream& operator>>(istream& stream, Bigint& v) {
    string s;
    stream >> s;
    v.read(s);
    return stream;
  }
  friend ostream& operator<<(ostream& stream, const Bigint& v) {
    if (v.sign == -1) stream << '-';
    stream << (v.a.empty() ? 0 : v.a.back());
    for (int i = (int)v.a.size() - 2; i >= 0; i--)
      stream << setw(nblock) << setfill('0') << v.a[i];
    return stream;
  }
  static vector<int> convert_base(const vector<int>& a, int old_digits,
                                  int new_digits) {
    vector<long long> p(max(old_digits, new_digits) + 1);
    p[0] = 1;
    for (int i = 1; i < (int)p.size(); i++) p[i] = p[i - 1] * base;
    vector<int> res;
    long long cur = 0;
    int cur_digits = 0;
    for (int i = 0; i < (int)a.size(); i++) {
      cur += a[i] * p[cur_digits];
      cur_digits += old_digits;
      while (cur_digits >= new_digits) {
        res.push_back(int(cur % p[new_digits]));
        cur /= p[new_digits];
        cur_digits -= new_digits;
      }
    }
    res.push_back((int)cur);
    while (!res.empty() && !res.back()) res.pop_back();
    return res;
  }
  static vector<long long> karatsuba(vector<long long>& a,
                                     vector<long long>& b) {
    int n = a.size();
    vector<long long> res(n << 1);
    if (n <= 32) {
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) res[i + j] += a[i] * b[j];
      return res;
    }
    int k = n >> 1;
    vector<long long> a1(a.begin(), a.begin() + k);
    vector<long long> a2(a.begin() + k, a.end());
    vector<long long> b1(b.begin(), b.begin() + k);
    vector<long long> b2(b.begin() + k, b.end());
    vector<long long> a1b1 = karatsuba(a1, b1);
    vector<long long> a2b2 = karatsuba(a2, b2);
    for (int i = 0; i < k; i++) a2[i] += a1[i];
    for (int i = 0; i < k; i++) b2[i] += b1[i];
    vector<long long> r = karatsuba(a2, b2);
    for (int i = 0; i < (int)a1b1.size(); i++) r[i] -= a1b1[i];
    for (int i = 0; i < (int)a2b2.size(); i++) r[i] -= a2b2[i];
    for (int i = 0; i < (int)r.size(); i++) res[i + k] += r[i];
    for (int i = 0; i < (int)a1b1.size(); i++) res[i] += a1b1[i];
    for (int i = 0; i < (int)a2b2.size(); i++) res[i + n] += a2b2[i];
    return res;
  }
  Bigint operator*(const Bigint& v) const {
    if ((max(this->a.size(), v.a.size()) * 9 + 5) / 6 <= 8192) {
      int r = 6;
      int t = round(pow(base, r));
      vector<int> ar = convert_base(this->a, nblock, r);
      vector<int> br = convert_base(v.a, nblock, r);
      vector<long long> a(ar.begin(), ar.end());
      vector<long long> b(br.begin(), br.end());
      while (a.size() < b.size()) a.push_back(0);
      while (b.size() < a.size()) b.push_back(0);
      while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0);
      vector<long long> c = karatsuba(a, b);
      Bigint res;
      res.sign = sign * v.sign;
      long long carry = 0;
      for (int i = 0; i < (int)c.size(); i++) {
        long long ncarry = c[i] + carry;
        res.a.push_back(ncarry % t);
        carry = ncarry / t;
      }
      while (carry) {
        res.a.push_back(carry % t);
        carry /= t;
      }
      res.a = convert_base(res.a, r, nblock);
      res.trim();
      return res;
    } else {
      vector<int> c = FFT::multiply(this->a, v.a, blockbase);
      Bigint res;
      res.sign = sign * v.sign;
      int carry = 0;
      for (int i = 0; i < (int)c.size(); i++) {
        int ncarry = c[i] + carry;
        res.a.push_back(ncarry % blockbase);
        carry = ncarry / blockbase;
      }
      assert(!carry);
      while (carry) {
        res.a.push_back(carry % blockbase);
        carry /= blockbase;
      }
      res.trim();
      return res;
    }
  }
  friend Bigint sqrt(const Bigint& a) {
    Bigint x0 = a, x1 = (a + 1) / 2;
    while (x1 < x0) {
      x0 = x1;
      x1 = (x1 + a / x1) / 2;
    }
    return x0;
  }
  friend Bigint pow(Bigint a, Bigint b) {
    if (b == Bigint(0)) return Bigint(1);
    Bigint T = pow(a, b / 2);
    if (b % 2 == 0) return T * T;
    return T * T * a;
  }
  friend Bigint pow(Bigint a, int b) { return pow(a, (Bigint(b))); }
  friend int log(Bigint a, int n) {
    int res = 0;
    while (a > Bigint(1)) {
      res++;
      a /= n;
    }
    return res;
  }
  template <class T>
  friend Bigint operator+(const T& v, const Bigint& a) {
    return a + v;
  }
  template <class T>
  friend Bigint operator-(const T& v, const Bigint& a) {
    return -a + v;
  }
  template <class T>
  friend Bigint operator*(const T& v, const Bigint& a) {
    return a * v;
  }
  template <class T>
  friend Bigint operator/(const T& v, const Bigint& a) {
    return Bigint(v) / a;
  }
  Bigint operator++() {
    (*this) += 1;
    return *this;
  }
  Bigint operator++(int) {
    (*this) += 1;
    return *this - 1;
  }
  Bigint operator--() {
    (*this) -= 1;
    return *this;
  }
  Bigint operator--(int) {
    (*this) -= 1;
    return *this + 1;
  }
};
void chemthan() {
  string s;
  cin >> s;
  if (s == "1") {
    cout << 1 << "\n";
    return;
  }
  int st = (int((s).size()) - 1) * (logl(10) / logl(3));
  st = max(0, st - 1);
  Bigint G(s);
  Bigint A = pow(Bigint(3), st);
  int res = INF, cnt = st;
  while (A < G) {
    Bigint T = A;
    for (int i = (0); i < (3 + 1); ++i) {
      if (G <= T) {
        chkmin(res, 3 * cnt + 2 * i);
      }
      T = T * 2;
    }
    A = A * 3;
    cnt++;
  }
  chkmin(res, 3 * cnt);
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}