int lower_solve(LL N) { return 5*(log(N)/log(4)) - 0.1; }

unordered_map<LL,int> memo;
int solve(LL N) {
    if (N == 0) return 0;
    if (memo.count(N)) return memo[N];
    int res = min(1000ll, N);
    for (int mul = 2; mul + 1 < res; mul++) {
        int add = N % mul;
        if (add + mul + 1 + lower_solve(N / mul) >= res) continue;
        int ris = add + mul + 1 + solve(N / mul);
        res = min(res, ris);
    }
    
    memo[N] = res;
    return res;
}