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 JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.stream.IntStream;

public class d {
    public static void main(String[] args) {
        FS in = new FS(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
//        StringBuilder inp = new StringBuilder();
//        inp.append("1");
//        for(int i = 1; i < 1_500_000; i++) inp.append("0");
//        inp.append("\n");
//        Scanner in = new Scanner(inp.toString());
//        System.err.println("here");
        long start = System.currentTimeMillis();
        
        String s = in.next();
        if(s.length() == 1) {
            int val = Integer.parseInt(s);
            long curr1 = 1;
            long min = 100000;
            for(int i = 0; i < 3; i++) {
                long curr2 = curr1;
                for(int j = 0; j < 3; j++) {
                    if(curr2 >= val) min = Math.min(min, 2*i+3*j);
                    curr2 *= 3;
                }
                curr1 *= 2;
            }
            System.out.println(Math.max(1, min));
            return;
        }
        
        Big orig = new Big(s.toCharArray());
        
        Big three = new Big(3);
        Big two = new Big(2);
        
        int tot = (int)(s.length()*Math.log(10)/Math.log(3))-3;
        Big pow = new Big(3).pow(tot);
        
        long min = Long.MAX_VALUE;
        for(int i = 0; i < 3; i++) {
            Big tmp = pow;
            int res = tot;
            while(tmp.compareTo(orig) < 0) {
                tmp = tmp.mult(three);
                res++;
            }
            min = Math.min(min, 2*i+3*res);
            pow = pow.mult(two);
        }
        System.err.println(System.currentTimeMillis()-start);
        start = System.currentTimeMillis();
        System.out.println(min);
        out.close();
    }
    
    
    
    static class Big implements Comparable<Big> {
        long[] vals;
        
        public Big(long val) {
            vals = new long[1];
            vals[0] = val;
        }
        
        public Big(char[] arr) {
            vals = new long[(arr.length+2)/3];
            for(int i = arr.length-1; i >= 0; i--) {
                vals[i/3] = vals[i/3]*10+arr[arr.length-i-1]-'0';
            }
        }
        
        public Big(long[] vals) {
            this.vals = vals;
        }
        
        public Big mult(Big o) {
            long[] res = FFT.multiply(vals, o.vals);
            for(int i = 0; i < res.length-1; i++) {
                res[i+1] += res[i]/1000;
                res[i] %= 1000;
            }
            if(res[res.length-1] >= 1000) {
                res = Arrays.copyOf(res, res.length+1);
                res[res.length-1] = res[res.length-2]/1000;
                res[res.length-2] %= 1000;
            }
            return new Big(res);
        }
        
        public Big pow(int pow) {
            if(pow == 0) return new Big(1);
            if(pow == 1) return this;
            Big tmp = this.pow(pow/2);
            tmp = tmp.mult(tmp);
            if(pow%2 == 1) tmp = tmp.mult(this);
            return tmp;
        }
        
        public int compareTo(Big o) {
            if(vals.length != o.vals.length) return vals.length - o.vals.length;
            for(int i = vals.length-1; i >= 0; i--) {
                if(vals[i] != o.vals[i]) {
                    return Long.compare(vals[i], o.vals[i]);
                }
            }
            return 0;
        }
    }
    
    static long MOD = (long)1e14;
    
    // SET maxk appropriately!!! ~log(maxn) //%
    static class FFT {

        static final int maxk = 19, maxn = (1 << maxk) + 1;
        // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
        //#
        static double[] wR = new double[maxn],
            wI = new double[maxn],
            rR = new double[maxn],
            rI = new double[maxn],
            aR = new double[maxn],
            aI = new double[maxn]; //$
        static int n, k, lastk = -1, dp[] = new int[maxn];

        static void fft(boolean inv) {
            if (lastk != k) {
                lastk = k;
                dp[0] = 0;
                for (int i = 1, g = -1; i < n; i++) {
                    if ((i & (i - 1)) == 0) {
                        g++;
                    }
                    dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
                }
                wR[1] = 1;
                wI[1] = 0;
                for (int t = 0; t < k - 1; t++) {
                    double a = Math.PI / n * (1 << (k - 1 - t));
                    double curR = Math.cos(a), curI = Math.sin(a);
                    int p2 = (1 << t), p3 = p2 * 2;
                    for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
                        wR[k] = wR[j];
                        wI[k] = wI[j];
                        wR[k + 1] = wR[j] * curR - wI[j] * curI;
                        wI[k + 1] = wR[j] * curI + wI[j] * curR;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                int d = dp[i];
                if (i < d) {
                    double tmp = aR[i];
                    aR[i] = aR[d];
                    aR[d] = tmp;
                    tmp = aI[i];
                    aI[i] = aI[d];
                    aI[d] = tmp;
                }
            }
            if (inv) {
                for (int i = 0; i < n; i++) {
                    aI[i] = -aI[i];
                }
            }
            for (int len = 1; len < n; len <<= 1) {
                for (int i = 0; i < n; i += len) {
                    int wit = len;
                    for (int it = 0, j = i + len; it < len; it++, i++, j++) {
                        double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
                        double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
                        wit++;
                        aR[j] = aR[i] - tmpR;
                        aI[j] = aI[i] - tmpI;
                        aR[i] += tmpR;
                        aI[i] += tmpI;
                    }
                }
            }
        }

        static long[] multiply(long[] a, long[] b) {
            int na = a.length, nb = b.length;
            for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {
            }
            for (int i = 0; i < n; ++i) {
                aR[i] = i < na ? a[i] : 0;
                aI[i] = i < nb ? b[i] : 0;
            }
            fft(false);
            aR[n] = aR[0];
            aI[n] = aI[0];
            double q = -1.0 / n / 4.0;
            for (int i = 0; i <= n - i; ++i) {
                double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
                double tmpI = aR[i] * aI[i] * 2;
                tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
                tmpI -= aR[n - i] * aI[n - i] * -2;
                aR[i] = -tmpI * q;
                aI[i] = tmpR * q;
                aR[n - i] = aR[i];
                aI[n - i] = -aI[i];
            }
            fft(true);
            long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
            for (int i = 0; i < n; i++) {
                ans[i] = Math.round(aR[i]) % MOD;
            }
            return ans;
        }

        static void fft2(double[][] xr, double[][] xi, boolean inv) {
            n = xr[0].length;
            k = Integer.numberOfTrailingZeros(n);
            for (int i = 0; i < xr.length; i++) {
                for (int j = 0; j < n; j++) {
                    aR[j] = xr[i][j];
                    aI[j] = xi[i][j];
                }
                fft(inv);
                for (int j = 0; j < n; j++) {
                    xr[i][j] = aR[j] / (inv ? n : 1);
                    xi[i][j] = aI[j] / (inv ? -n : 1);
                }
            }
            n = xr.length;
            k = Integer.numberOfTrailingZeros(n);
            for (int j = 0; j < xr[0].length; j++) {
                for (int i = 0; i < n; i++) {
                    aR[i] = xr[i][j];
                    aI[i] = xi[i][j];
                }
                fft(inv);
                for (int i = 0; i < n; i++) {
                    xr[i][j] = aR[i] / (inv ? n : 1);
                    xi[i][j] = aI[i] / (inv ? -n : 1);
                }
            }
        }

        static long[][] multiply2(long[][] a, long[][] b) {
            int n1, n2;
            for (n1 = 1; n1 < a.length + b.length - 1; n1 <<= 1) {
            }
            for (n2 = 1; n2 < a[0].length + b[0].length - 1; n2 <<= 1) {
            }
            double[][] ar = new double[n1][n2], ai = new double[n1][n2];
            double[][] br = new double[n1][n2], bi = new double[n1][n2];
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    ar[i][j] = a[i][j];
                }
            }
            for (int i = 0; i < b.length; i++) {
                for (int j = 0; j < b[i].length; j++) {
                    br[i][j] = b[i][j];
                }
            }
            fft2(ar, ai, false);
            fft2(br, bi, false);
            for (int i = 0; i < n1; i++) {
                for (int j = 0; j < n2; j++) {
                    double r1 = ar[i][j], r2 = br[i][j];
                    double i1 = ai[i][j], i2 = bi[i][j];
                    double real = r1 * r2 - i1 * i2;
                    ai[i][j] = i1 * r2 + i2 * r1;
                    ar[i][j] = real;
                }
            }
            fft2(ar, ai, true);
            long[][] result = new long[n1 = a.length + b.length - 1][n2 = a[0].length + b[0].length - 1];
            for (int i = 0; i < n1; i++) {
                for (int j = 0; j < n2; j++) {
                    result[i][j] = Math.round(ar[i][j]);
                }
            }
            return result;
        }
        //#

        static long[] multiplyPrecise(long[] a, long[] b) {
            long k = (long) (Math.sqrt(MOD));
            long[] a1 = new long[a.length], a2 = new long[a.length];
            long[] b1 = new long[b.length], b2 = new long[b.length];
            for (int i = 0; i < a.length; i++) {
                a1[i] = a[i] % k;
                a2[i] = a[i] / k;
            }
            for (int i = 0; i < b.length; i++) {
                b1[i] = b[i] % k;
                b2[i] = b[i] / k;
            }
            long[] r11 = multiply(a1, b1), r12 = multiply(a1, b2), r21 = multiply(a2, b1), r22 = multiply(a2, b2);
            long[] res = new long[r11.length];
            for (int i = 0; i < res.length; i++) {
                res[i] = (k * k * r22[i] + k * (r12[i] + r21[i]) + r11[i]) % MOD;
            }
            return res;
        }
        //$
        //#

        static long[] multiplyOr(long[] eq1, long[] eq2) {
            int n = Math.max(eq1.length, eq2.length);
            if ((n & (n - 1)) != 0) {
                n = Integer.highestOneBit(n) * 2;
            }
            eq1 = fftOr(eq1, n, false);
            eq2 = fftOr(eq2, n, false);
            for (int i = 0; i < eq1.length; i++) {
                eq1[i] *= eq2[i];
            }
            eq1 = fftOr(eq1, n, true);
            return eq1;
        }
        //$
        // To use: FFT both, product, iFFT (n is next power of 2)

        static long[] fftOr(long[] arr, int n, boolean invert) {
            long[] ans = Arrays.copyOf(arr, n);
            for (int b = 1; b < n; b <<= 1) {
                for (int i = 0; i < n; i++) {
                    if ((i & b) != 0) {
                        continue;
                    }
                    ans[i + b] += invert ? -ans[i] : ans[i];
                }
            }
            return ans;
        }

        static long[] fftXor(long[] arr, int n, boolean invert) {
            long[] ans = Arrays.copyOf(arr, n);
            for (int b = 1; b < n; b <<= 1) {
                for (int i = 0; i < n; i++) {
                    if ((i & b) != 0) {
                        continue;
                    }
                    long u = ans[i], v = ans[i + b];
                    ans[i] = u + v;
                    ans[i + b] = u - v;
                }
            }
            if (invert) {
                for (int i = 0; i < n; i++) {
                    ans[i] /= n;
                }
            }
            return ans;
        }
    }
    
    static class FS {

        BufferedReader in;
        StringTokenizer token;
        
        public FS(InputStream str) {
            in = new BufferedReader(new InputStreamReader(str));
        }
        
        public String next() {
            if (token == null || !token.hasMoreElements()) {
                try {
                    token = new StringTokenizer(in.readLine());
                } catch (IOException ex) {
                }
                return next();
            }
            return token.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}