mem = {}

def count(n):
    if n in mem:
        return mem[n]
    if n <= 1:
        return 0
    mem[n] = int(min(n, count(n//2) + 1 + (n % 2), count(n//3) + 1 + (n % 3)))
    return mem[n]

for i in  (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
          27, 30, 81, 82, 101, 772, 768, 32, 64, 256, 1024, 2**16, 2**32,
          2**63, 2**64-1, 123, 1234, 12345, 123456, 1234567890, 12345678901234567890,
          100, 1000, 10000, 100000, 999983, 999995, 999999, 1000000, 1000003,
          1E9, 1E12,  1E15-1, 1E15, 1E15+1,
          214013, 134775813, 6364136223846793005, 1442695040888963407):
    print("N = {}; Answer = {}".format(i,count(i)))