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>
#pragma GCC optimize(3)
using namespace std;
const double PI = acos(-1.0);
namespace fft {
struct num {
  double x, y;
  num() { x = y = 0; }
  num(double x, double y) : x(x), y(y) {}
};
inline num operator+(num a, num b) { return num(a.x + b.x, a.y + b.y); }
inline num operator-(num a, num b) { return num(a.x - b.x, a.y - b.y); }
inline num operator*(num a, num b) {
  return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline num conj(num a) { return num(a.x, -a.y); }
long long base = 1;
vector<num> roots = {{0, 0}, {1, 0}};
vector<long long> rev = {0, 1};
const double PI = acosl(-1.0);
void ensure_base(long long nbase) {
  if (nbase <= base) return;
  rev.resize(1 << nbase);
  for (long long i = 0; i < (1 << nbase); i++)
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  roots.resize(1 << nbase);
  while (base < nbase) {
    double angle = 2 * PI / (1 << (base + 1));
    for (long long i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      double angle_i = angle * (2 * i + 1 - (1 << base));
      roots[(i << 1) + 1] = num(cos(angle_i), sin(angle_i));
    }
    base++;
  }
}
void fft(vector<num> &a, long long n = -1) {
  if (n == -1) n = a.size();
  assert((n & (n - 1)) == 0);
  long long zeros = __builtin_ctz(n);
  ensure_base(zeros);
  long long shift = base - zeros;
  for (long long i = 0; i < n; i++)
    if (i < (rev[i] >> shift)) swap(a[i], a[rev[i] >> shift]);
  for (long long k = 1; k < n; k <<= 1) {
    for (long long i = 0; i < n; i += 2 * k) {
      for (long long j = 0; j < k; j++) {
        num z = a[i + j + k] * roots[j + k];
        a[i + j + k] = a[i + j] - z;
        a[i + j] = a[i + j] + z;
      }
    }
  }
}
vector<num> fa, fb;
vector<long long> multiply(vector<long long> &a, vector<long long> &b) {
  long long need = a.size() + b.size() - 1;
  long long nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  long long sz = 1 << nbase;
  if (sz > (long long)fa.size()) fa.resize(sz);
  for (long long i = 0; i < sz; i++) {
    long long x = (i < (long long)a.size() ? a[i] : 0);
    long long y = (i < (long long)b.size() ? b[i] : 0);
    fa[i] = num(x, y);
  }
  fft(fa, sz);
  num r(0, -0.25 / sz);
  for (long long i = 0; i <= (sz >> 1); i++) {
    long long j = (sz - i) & (sz - 1);
    num z = (fa[j] * fa[j] - conj(fa[i] * fa[i])) * r;
    if (i != j) fa[j] = (fa[i] * fa[i] - conj(fa[j] * fa[j])) * r;
    fa[i] = z;
  }
  fft(fa, sz);
  vector<long long> res(need);
  for (long long i = 0; i < need; i++) res[i] = fa[i].x + 0.5;
  return res;
}
vector<long long> multiply_mod(vector<long long> &a, vector<long long> &b,
                               long long m, long long eq = 0) {
  long long need = a.size() + b.size() - 1;
  long long nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  long long sz = 1 << nbase;
  if (sz > (long long)fa.size()) fa.resize(sz);
  for (long long i = 0; i < (long long)a.size(); i++) {
    long long x = (a[i] % m + m) % m;
    fa[i] = num(x & ((1 << 15) - 1), x >> 15);
  }
  fill(fa.begin() + a.size(), fa.begin() + sz, num{0, 0});
  fft(fa, sz);
  if (sz > (long long)fb.size()) fb.resize(sz);
  if (eq)
    copy(fa.begin(), fa.begin() + sz, fb.begin());
  else {
    for (long long i = 0; i < (long long)b.size(); i++) {
      long long x = (b[i] % m + m) % m;
      fb[i] = num(x & ((1 << 15) - 1), x >> 15);
    }
    fill(fb.begin() + b.size(), fb.begin() + sz, num{0, 0});
    fft(fb, sz);
  }
  double ratio = 0.25 / sz;
  num r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
  for (long long i = 0; i <= (sz >> 1); i++) {
    long long j = (sz - i) & (sz - 1);
    num a1 = (fa[i] + conj(fa[j]));
    num a2 = (fa[i] - conj(fa[j])) * r2;
    num b1 = (fb[i] + conj(fb[j])) * r3;
    num b2 = (fb[i] - conj(fb[j])) * r4;
    if (i != j) {
      num c1 = (fa[j] + conj(fa[i]));
      num c2 = (fa[j] - conj(fa[i])) * r2;
      num d1 = (fb[j] + conj(fb[i])) * r3;
      num d2 = (fb[j] - conj(fb[i])) * r4;
      fa[i] = c1 * d1 + c2 * d2 * r5;
      fb[i] = c1 * d2 + c2 * d1;
    }
    fa[j] = a1 * b1 + a2 * b2 * r5;
    fb[j] = a1 * b2 + a2 * b1;
  }
  fft(fa, sz);
  fft(fb, sz);
  vector<long long> res(need);
  for (long long i = 0; i < need; i++) {
    long long aa = fa[i].x + 0.5;
    long long bb = fb[i].x + 0.5;
    long long cc = fa[i].y + 0.5;
    res[i] = (aa + ((bb % m) << 15) + ((cc % m) << 30)) % m;
  }
  return res;
}
vector<long long> square_mod(vector<long long> &a, long long m) {
  return multiply_mod(a, a, m, 1);
}
};  // namespace fft
void multiply(vector<long long> &a, long long b) {
  long long carry = 0;
  for (long long i = 0; i < (long long)a.size(); i++) {
    carry += a[i] * b;
    a[i] = carry % 1000;
    carry /= 1000;
  }
  while (carry > 0) {
    a.push_back(carry % 1000);
    carry /= 1000;
  }
}
void divide(vector<long long> &a, long long b) {
  long long md = 0;
  for (long long i = (long long)a.size() - 1; i >= 0; i--) {
    md = 1000 * md + a[i];
    a[i] = md / b;
    md %= b;
  }
  assert(md == 0);
  while (!a.empty() && a.back() == 0) {
    a.pop_back();
  }
}
bool is_less(const vector<long long> &a, const vector<long long> &b) {
  if (a.size() != b.size()) return a.size() < b.size();
  for (long long i = (long long)a.size() - 1; i >= 0; i--)
    if (a[i] != b[i]) return a[i] < b[i];
  return false;
}
vector<long long> sp3;
void get_p3(long long p3) {
  if (p3 <= 0) return;
  if (p3 & 1) {
    get_p3(p3 - 1);
    multiply(sp3, 3);
  } else {
    get_p3(p3 >> 1);
    sp3 = fft::multiply(sp3, sp3);
    long long carry = 0;
    for (long long i = 0; i < (long long)sp3.size(); i++) {
      carry += sp3[i];
      sp3[i] = carry % 1000;
      carry /= 1000;
    }
    while (carry > 0) {
      sp3.push_back(carry % 1000);
      carry /= 1000;
    }
  }
}
string str;
int main() {
  cin >> str;
  if (str == "1") {
    puts("1");
    return 0;
  }
  long long len = (long long)str.size();
  vector<long long> v;
  long long carry = 0, cnt = 0, d = 1;
  for (long long i = len - 1; i >= 0; i--) {
    cnt++;
    carry += (long long)(str[i] - '0') * d;
    d *= 10;
    if (cnt % 3 == 0 || i == 0) {
      v.push_back(carry);
      carry = 0;
      d = 1;
    }
  }
  long long p3 = (long long)(logl(10) * (len - 1) / logl(3));
  sp3.assign(1, 1);
  get_p3(p3);
  long long ans = 3 * p3;
  while (is_less(sp3, v)) {
    if (ans <= 3)
      sp3[0] = ans + 1;
    else {
      if (ans % 3 == 0) {
        divide(sp3, 3);
        multiply(sp3, 4);
      } else {
        divide(sp3, 2);
        multiply(sp3, 3);
      }
    }
    ans++;
  }
  printf("%I64d\n", ans);
  return 0;
}